Докажите неравенство для натуральных чисел в бесконечной последователь

Очевидно, что последовательность не убывает. Действительно, неравенство $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 класса: 167188