So I've been stuck on Ramsey theory for a few days now and ran across this cool theorem. If you have a sequence of n²+1 distinct numbers, then you are guaranteed to have a monotonically increasing (or decreasing) subsequence of length n + 1 or more.
Of course I had to try this. Let n = 3, so that n²+1 = 10. The largest subsequence has to be of length n+1 = 4, or greater. Let's do an example.
I took a random permutation of {0..9} and got
π{0..9} = {0 9 7 8 1 3 5 4 2 6}
The longest increasing subsequence is {0 1 3 5 6}, which is of length 5.
The longest decreasing subsequence is {9 8 5 4 2}, which is also of length 5.
So in this case the theorem holds up, as it must. Try it yourself!
This theorem of subsequence length was shown in a 1935 paper by Paul Erdós and Szekeres. This was a cornerstone paper in the field of combinatorics now called Ramsey Theory. A general discussion of such subsequences can be found in Martin Aigner and Günter Ziegler's "Proofs from the Book," Springer-Verlag, (c)1998.
(Thanks to user Clockmaker who pointed out the Hungarian orthography of Paul Erdós's name here, as well as typo detection.)