I really liked this problem that my friend Shamile gave during dinner:

Consider 50 people lined up in a random order. Show that there exists a subsequence of length 8 such that the height is non-increasing or non-decreasing.

The solution is quite elegant. Assign an ordered pair to person in the line such that the first coordinate is the length of the *longest subsequence which is increasing from person *, and the second coordinate is the length of the longest subsequence which is decreasing from the same person.

Let’s assume by contradiction that the longest such length is less than 8; this implies that the set of acceptable coordinates is from (0, 0) to (7,7). There is only 49 total combinations, so by pigeonhole principle, there exists a pair of the same number. But this cannot be! The rest is left to the reader.