Problem
COM-B1-M05-P024 Monotone Subsequence
#24
★★★★★ Level 5 of 5
Prove that among any \(10\) distinct real numbers, there is an increasing subsequence of length \(4\) or a decreasing subsequence of length \(4\).
For each position, record two lengths: best increasing and best decreasing subsequence starting there.
For each number \(a_i\), write \((u_i,d_i)\), where \(u_i\) is the maximum length of an increasing subsequence starting at \(a_i\), and \(d_i\) the maximum length of a decreasing one. If there is no monotone subsequence of length \(4\), then \(u_i,d_i\in\{1,2,3\}\), only \(9\) pairs. Among \(10\) numbers, two pairs coincide; let \(i
Classic strong finale of the module.