Задача
COM-B1-M05-P024 Монотонная подпоследовательность
Докажите, что среди любых \(10\) различных действительных чисел найдётся возрастающая подпоследовательность длины \(4\) или убывающая подпоследовательность длины \(4\).
Для каждой позиции запишите пару длин: лучшая возрастающая и лучшая убывающая подпоследовательность, начинающаяся там.
Для каждого числа \(a_i\) запишем пару \((u_i,d_i)\), где \(u_i\) — максимальная длина возрастающей подпоследовательности, начинающейся с \(a_i\), а \(d_i\) — максимальная длина убывающей, начинающейся с \(a_i\). Если нет монотонной подпоследовательности длины \(4\), то \(u_i,d_i\in\{1,2,3\}\), всего \(9\) пар. Для \(10\) чисел две пары совпадают: пусть \(i
Классический сильный финал модуля.