Less Than Maximum Property
if a < maximum value in stack xs, then maximum value in stack [ a, xs ] = maximum value in stack xs
If we know that some value a is less than the maximum value of some list xs, then the maximum value of the list that includes a and xs is the maximum value of xs.
Examples
if 5 < maximum value in stack [ 7, [ ] ], then maximum value in stack [ 5, [ 7, [ ] ] ] = maximum value in stack [ 7, [ ] ]
if 1 < maximum value in stack [ 2, [ 3, [ 4, [ ] ] ] ], then maximum value in stack [ 1, [ 2, [ 3, [ 4, [ ] ] ] ] ] = maximum value in stack [ 2, [ 3, [ 4, [ ] ] ] ]
if 1248 < maximum value in stack [ 2000, [ 3300, [ 1450, [ ] ] ] ], then maximum value in stack [ 1248, [ 2000, [ 3300, [ 1450, [ ] ] ] ] ] = maximum value in stack [ 2000, [ 3300, [ 1450, [ ] ] ] ]
If we know the maximum value of some list, this property can tell us the maximum value of a new larger list. We can use this property many times to help us to prove claims about large lists.
For instance, in the first example, we know that the maximum of the list [7, []] is simply 7. Then, since 5 is less than 7, we claim that the maximum of [5, [7,[]]] remains 7.
If y is less than the maximum value of list [12, [3, [7, []]]], then what is the maximum value of list [y, [12, [3, [7, []]]]] ?
Comments
Please log in to add comments