Олимпиада Туймаада по математике. Младшая лига. 2015 год

Существует ли возрастающая последовательность натуральных чисел $(a_n)$ такая, что среди разностей $a_{n+1}-a_n$ встречаются все натуральные числа ровно по одному разу, а среди разностей {$a_{n+2}-a_n$} встречаются только натуральные числа, большие 2015, причем тоже ровно по одному разу? ( А. Голованов )

Комментарий/решение

Ответ: нет.

Предположим, что такая последовательность $(a_n)$ существует. Обозначим

$$d_n=a_{n+1}-a_n,\qquad e_n=a_{n+2}-a_n=d_n+d_{n+1}.$$

По условию $d_n$ — перестановка всех натуральных чисел, а $e_n$ — перестановка всех натуральных чисел, больших $2015$.

Рассмотрим сумму первых $N$ вторых разностей:

$$\sum_{i=1}^N e_i = a_{N+1}+a_{N+2}-a_1-a_2.$$

Так как $e_i$ — все числа $>2015$ ровно по одному разу, то

$$\sum_{i=1}^N e_i \ge N\cdot 2016 + \frac{N(N-1)}2.$$

С другой стороны, $a_{N+1}=a_1+\sum_{i=1}^N d_i$, и поскольку $d_i$ — перестановка натуральных чисел,

$$\sum_{i=1}^N d_i \ge 1+2+\dots+N = \frac{N(N+1)}2.$$

Аналогично $\sum_{i=1}^{N+1} d_i \ge \frac{(N+1)(N+2)}2$. Поэтому

$$a_{N+1}+a_{N+2} \ge 2a_1 + \frac{N(N+1)}2 + \frac{(N+1)(N+2)}2 = 2a_1 + (N+1)^2.$$

Следовательно,

$$\sum_{i=1}^N e_i \ge a_1 + (N+1)^2 - a_2.$$

Таким образом, должно выполняться

$$a_1 + (N+1)^2 - a_2 \ge N\cdot 2016 + \frac{N(N-1)}2.$$

При $N=2016$ получаем

$$a_1 + 2017^2 - a_2 \ge 2016\cdot 2016 + \frac{2016\cdot 2015}2 = 6\,095\,376.$$

Но $a_2-a_1=d_1\ge 1$, поэтому $a_1-a_2\le -1$, и левая часть не превосходит $2017^2-1=4\,068\,288$, что меньше $6\,095\,376$. Противоречие.

Значит, такой последовательности не существует.

Самое худшее решение что я видел, глаза кровью обливаются