Последовательности и прогрессии на ММО

Очевидно, что последовательность не убывает. Действительно, неравенство противоречило бы выбору Также понятно, что любое число повторяется не более, чем дважды, иначе в последовательности найдутся три одинаковых числа, а они образуют триплет. Теперь легко видеть, что если число впервые встречается в последовательности в качестве то

Таким образом, для любого натурального верно равенство Заметим, что тогда достаточно доказать требуемое неравенство только для нечетных индексов:

Положим Тогда нужно доказать, что

Отметим, что последовательность обладает тем свойством, что при очередной член последовательности - минимальное натуральное число, которое не образует триплет с парами чисел из где пара может иметь вид При этом то есть строго возрастает, в отличие от

Пусть - минимальное натуральное число, для которого требуемое неравенство неверно, то есть Это означает, что среди чисел от до содержится ровно член последовательности, поскольку при по предположению имеем

Обозначим через количество чисел в промежутке от 1 до не принадлежащих последовательности Тогда

Обозначим эти числа В силу минимальности каждого из для любого найдутся такие числа где что - триплет. При это можно считать, что - наибольший элемент в триплете, иное бы противоречило выбору наименьшего элемента последовательности большего Отсюда Тогда число способов выбрать пару не превосходит то есть не больше способов выбрать два различных индекса из В то же время парами нужно обеспечить чисел Полученное противоречие завершает решение.