Математикадан 56-шы халықаралық олимпиада, 2015 жыл, Чиангмай

$a_1$, $a_2$, $\ldots$ бүтін сандар тізбегі келесі шарттарды қанағаттандырады:
(i) барлық $j \ge 1$ үшін $1 \le a_j \le 2015$;
(ii) барлық $1 \le k < \ell$ үшін $k+a_k \ne \ell + a_{\ell}$.
$n> m \ge N$ болатын барлық бүтін $m$ және $n$ үшін $\left| {\sum\limits_{j = m + 1}^n {({a_j} - b) \le {{1007}^2}} } \right|$ орындалатындай натурал $b$ және $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$.