МОШ 2023, 11 класс, задача 6
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Дана бесконечная последовательность , состоящая из натуральных чисел. Известно, что и при число — минимальное натуральное число такое, что среди чисел нет трёх, образующих триплет. Докажите, что для любого .
(Б. Г. Бутырин)
Решение. Очевидно, что последовательность не убывает. Действительно, неравенство противоречило бы выбору . Также понятно, что любое число повторяется не более, чем дважды, иначе в последовательности найдутся три одинаковых числа, а они образуют триплет. Теперь легко видеть, что если число впервые встречается в последовательности в качестве , то .
Таким образом, для любого натурального числа верно равенство . Заметим, что тогда достаточно доказать требуемое неравенство только для нечетных индексов:
Положим . Тогда нужно доказать, что
Отметим, что последовательность обладает тем свойством, что при очередной член последовательности — минимальное натуральное число, которое не образует триплет с парами чисел из , где пара может иметь вид . При этом , то есть строго возрастает, в отличие от .
Пусть — минимальное натуральное число, для которого требуемое неравенство неверно, то есть
Это означает, что среди чисел от до содержится ровно член последовательности, поскольку при по предположению имеем
Обозначим через количество чисел в промежутке от до , не принадлежащих последовательности . Тогда
Обозначим эти числа через , .
В силу минимальности каждого из для любого найдутся такие числа , , где , что — триплет. При этом можно считать, что — наибольший элемент в триплете, иное бы противоречило выбору наименьшего элемента последовательности , большего . Отсюда .
Тогда число способов выбрать пару не превосходит , то есть не больше количества способов выбрать два различных индекса из . В то же время парами нужно обеспечить чисел . Полученное противоречие завершает решение.