Задача
ALG-B2-M01-P021 Длинные монотонные отрезки
Бесконечная последовательность попарно различных действительных чисел \(a_1,a_2,\ldots\) имеет свойство: для каждого \(k\) член \(a_k\) входит в некоторый монотонный подряд идущий отрезок длины \(k+1\). Докажите, что с некоторого места вся последовательность монотонна.
Подсказка 1. Назовите индекс плохим, если направление меняется в нём.
Подсказка 2. Длинный монотонный отрезок не может содержать три члена вокруг плохого индекса.
Назовём \(i\ge2\) плохим, если \(a_{i-1} Предположим, что плохих индексов бесконечно много, и выберем один плохой индекс \(k\). Возьмём любое \(n>k\). По условию \(a_n\) входит в монотонный отрезок длины \(n+1\). Такой отрезок не может содержать одновременно \(a_{k-1},a_k,a_{k+1}\), потому что в этих трёх членах направление меняется. Так как \(n+1\) очень длинен и содержит \(a_n\), он не может начинаться настолько рано, чтобы включить \(a_{k-1}\); следовательно, он обязан содержать \(a_n,a_{n+1},a_{n+2}\). Тогда индекс \(n+1\) не плохой. Итак, для всех \(n>k\) индекс \(n+1\) не плохой, что противоречит бесконечности плохих индексов. Значит, плохих индексов конечное число, и хвост последовательности монотонен.
A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.
F. Обоснование сложности. Финальный уровень 8: требуется заменить монотонность анализом плохих индексов.
G. Почему это не одноходовая задача. Нельзя просто выбрать самый длинный отрезок; нужно понять, что плохие индексы исчезают.