Subsequences of Heights

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 (a_i, b_i) to person i in the line such that the first coordinate is the length of the longest subsequence which is increasing from person i, 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.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.