|
|
 |
Условие
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Дана бесконечная последовательность $(a_n)$, состоящая из натуральных чисел. Известно, что $a_1=a_2=1$ и при $n > 2$ число $a_n$ — минимальное натуральное число такое, что среди чисел $a_1,a_2,\ldots,a_n$ нет трёх, образующих триплет. Докажите, что $a_n\leqslant \frac{n^2+7}{8}$ для любого $n$.Решение
Очевидно, что последовательность не убывает. Действительно, неравенство $a_{n} > a_{n+1}$ противоречило бы выбору $a_{n}$. Также понятно, что любое число повторяется не более чем дважды, иначе в последовательности найдутся три одинаковых числа, а они образуют триплет. Теперь легко видеть, что если число $c$ впервые встречается в последовательности в качестве $a_{n}$, то $a_{n+1}=a_{n}=c$.Таким образом, для любого натурального числа $k$ верно равенство $a_{2 k-1}=a_{2 k}$. Заметим, что тогда достаточно доказать требуемое неравенство только для нечётных индексов: $$ a_{2 k}=a_{2 k-1} \leqslant \frac{(2 k-1)^{2}+7}{8} \leqslant \frac{(2 k)^{2}+7}{8}. $$
Положим $b_{k}=a_{2 k-1}$. Тогда нужно доказать, что $$ b_{k} \leqslant \frac{(2 k-1)^{2}+7}{8}=\frac{k(k-1)}{2}+1. $$
Отметим, что последовательность $(b_{n})$ обладает тем свойством, что при $k>1$ очередной член последовательности $b_{k}$ — минимальное натуральное число, которое не образует триплет с парами чисел из $\{b_{1}, \ldots, b_{k-1}\}$, где пара может иметь вид $(b_i,b_i)$. При этом $b_{k} > b_{k-1}$, то есть $(b_{n})$ строго возрастает, в отличие от $(a_{n})$.
Пусть $n$ — минимальное натуральное число, для которого требуемое неравенство неверно, то есть $b_{n} > \frac{n(n-1)}{2}+1$. Это означает, что среди чисел от 1 до $\frac{n(n-1)}{2}+1$ содержится ровно $n-1$ член последовательности, поскольку при $m < n$ по предположению имеем $$b_{m} \leqslant \frac{m(m-1)}{2}+1 < \frac{n(n-1)}{2}+1.$$ Обозначим через $s$ количество чисел в промежутке от 1 до $\frac{n(n-1)}{2}+1$, не принадлежащих последовательности $(b_n)$. Тогда $$ s=\frac{n(n-1)}{2}+1-(n-1)=\frac{(n-1)(n-2)}{2}+1=C_{n-1}^{2}+1. $$ Обозначим эти числа через $d_{i}$, $1 \leqslant i \leqslant s$.
В силу минимальности каждого из $b_{m}$ для любого $1 \leqslant k \leqslant s$ найдутся такие числа $b_{i_{k}}$, $b_{j_{k}}$, где $i_{k} \leqslant j_{k} \leqslant n-1$, что $(b_{i_{k}}, b_{j_{k}}, d_{k})$ — триплет. При этом можно считать, что $d_k$ — наибольший элемент в триплете, иное бы противоречило выбору наименьшего элемента последовательности $(b_n),$ большего $d_k$. Отсюда $i_{k} < j_{k}$.
Тогда число способов выбрать пару $(i_{k}, j_{k})$ не превосходит $C_{n-1}^{2}$, то есть не больше количества способов выбрать два различных индекса из $\{1,2, \ldots, n-1\}$. В то же время парами $(i_{k}, j_{k})$ нужно обеспечить $s > C_{n-1}^{2}$ чисел $d_i$. Полученное противоречие завершает решение.
Комментарий. См. также решение задачи 6 для 9 класса: 67188
