56-я Международная Математическая OлимпиадаТаиланд, Чиангмай, 2015 год

Последовательность ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$ целых чисел удовлетворяет следующим условиям:
(i) $1\le {{a}_{j}}\le 2015$ для всех $j\ge 1$;
(ii) $k+{{a}_{k}}\ne l+{{a}_{l}}$ для всех $1\le k < l$.
Докажите, что существуют два положительных целых числа $b$ и $N$ таких, что $\left| \sum\limits_{j=m+1}^{n}{\left( {{a}_{j}}-b \right)} \right|\le {{1007}^{2}}$ для всех целых чисел $m$ и $n$, удовлетворяющих условию $n > m\ge N$.

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

Для удобства замените (i) на $0\leq a_j\leq n=2014$.

Пусть $b_i=a_i+i$, поэтому $i\leq b_i\leq i+n$. Тогда последовательность $b_i$ должна содержать все неотрицательные целые числа, кроме $b\leq n$ из них. Пусть $B$ — набор из $b$ чисел. Выберите любое $N$, большее всех чисел в $B$.

Пусть $S_i=\{b_0,\ldots, b_i\}$ и $T_i=\{0,\ldots, i\}$. Оценим сумму $\sum_N^{N+m} b_i$. Обратите внимание, что $T_{N+m}\setminus B\subset S_{N+m}\subset T_{N+m+n}\setminus B$. Так как $S_{N+m}$ содержит ровно $N+m+1$ элементов, а $T_{N+m+n}\setminus B$ содержит $N+m+n+1-b$, то существует ровно $n-b$ элементов из $T_{N+m+n}\setminus T_{N+m}$, которых НЕТ в $S_{N+m}$. Таким образом, максимальное значение $\sum_N^{N+m} b_i$ равно

\[\sum_{N+m+n-b+1}^{N+m+n} i +\sum_{N+b}^{N+m} i

\], когда $m\geq b$ (если $m<b$, $\sum_N^{N+m}(a_i-b)\leq b(n-b)$ является непосредственным). Таким образом, $\sum_N^{N+m}(a_i-b)=\sum_N^{N+m}(b_i-i-b)\leq b(n-b)$. Что касается минимума, обратите внимание, что каждый элемент в $S_{N}$ равен $\leq N+n$, поэтому минимальное значение $\sum_N^{N+m} b_i$ равно

\[\sum_{N+n+1}^{N+m+b} i + \sum_{N}^{N+n-b} i

\]когда $m\geq n-b$. Если $m<n-b$, то $\sum_N^{N+m}(a_i-b)\geq -b(n-b)$ является непосредственным. В противном случае дополнительные арифметические манипуляции снова дадут $\sum_N^{N+m}(a_i-b)\geq -b(n-b)$. Поэтому $\left\vert\sum_N^{N+m}(a_i-b)\right\vert\leq b(n-b)\leq 1007^2$.