Задача
COM-B2-M04-P018 Монотонная подпоследовательность
Дана последовательность из \(n^2+1\) различных действительных чисел. Докажите, что в ней найдётся возрастающая подпоследовательность длины \(n+1\) или убывающая подпоследовательность длины \(n+1\).
Для каждого элемента запишите две величины: длину лучшей возрастающей подпоследовательности, заканчивающейся в нём, и длину лучшей убывающей подпоследовательности, заканчивающейся в нём.
Для каждого места \(i\) обозначим через \(p_i\) длину наибольшей возрастающей подпоследовательности, заканчивающейся на \(a_i\), а через \(q_i\) — длину наибольшей убывающей подпоследовательности, заканчивающейся на \(a_i\).
Предположим, что нет ни возрастающей, ни убывающей подпоследовательности длины \(n+1\). Тогда все пары \((p_i,q_i)\) принимают значения из множества \(\{1,\ldots,n\}\times\{1,\ldots,n\}\), то есть возможны только \(n^2\) пар.
Покажем, что пары для разных \(i\) различны. Если \(i
Но элементов \(n^2+1\), а различных пар не больше \(n^2\). Противоречие. Значит, нужная подпоследовательность существует.
Классическая сильная задача: экстремальные длины подпоследовательностей плюс принцип Дирихле.