Increasing or decreasing subsequence
|Contact| |Front page| |Contents| |Up| |Store|
Copyright © 1996-2011 Alexander BogomolnyAssume that the result is false. For each number x in the sequence, form the ordered pair
If a < b, then a, together with the longest increasing subsequence beginning with b, is an increasing subsequence of length
(There is an interactive illustration of the above result and another one, perhaps a little more entertaining. According to Erickson, the problem is now known as the Erdös-Szekeres theorem.
References
- M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
- A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, p. 61
- M. Erickson, Beautiful Mathematics, MAA, 2011
- M. Gardner, The Last Recreations, Copernicus, 1997
![]()
|Contact| |Front page| |Contents| |Up| |Store|
Copyright © 1996-2011 Alexander Bogomolny| 40614807 |

