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.)