Problem
COM-B2-M04-P018 A Monotone Subsequence
A sequence of \(n^2+1\) distinct real numbers is given. Prove that it contains an increasing subsequence of length \(n+1\) or a decreasing subsequence of length \(n+1\).
For each element, record two values: the length of the best increasing subsequence ending there and the length of the best decreasing subsequence ending there.
For each position \(i\), let \(p_i\) be the length of the longest increasing subsequence ending at \(a_i\), and let \(q_i\) be the length of the longest decreasing subsequence ending at \(a_i\).
Suppose there is neither an increasing nor a decreasing subsequence of length \(n+1\). Then all pairs \((p_i,q_i)\) take values in \(\{1,\ldots,n\}\times\{1,\ldots,n\}\), so only \(n^2\) pairs are possible.
We show that pairs for different indices are distinct. If \(i
But there are \(n^2+1\) elements and at most \(n^2\) possible pairs. Contradiction. Therefore the required subsequence exists.
A classic strong problem: extremal subsequence lengths plus the pigeonhole principle.