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$.

\[ a_k+k = b_k \ \to \ b_k \ne b_l \mid \forall \ k \ne l\]

Утверждение: С какого то момента $b_i$ станет биекцией

\[\]

Доказательство:

\[ X \subset \{ \ i \mid \forall \ 1\leq i \leq n+2015\ \} \mid X \cap \{ \ b_i \mid \forall \ 1 \leq i \leq n \ \} = 0 \ \ \to \ 1 \leq \mid X \mid = x \leq 2015 \quad \blacksquare \]

Докажем что $ N > 2015 \mid b=x $ удовлетворяет нашим условиям

\[ \left | \sum \limits_{j=m+1}^{n} (a_j-x) \right | = \left | \sum \limits_{j=m+1}^{n} (b_j - j-x) \right | \quad ( \ \star \ ) \]

Рассмотрим промежутки $:$

\[ [1, \dots, m+1 ] \cup [m+2, \dots, n+2015 ] \mid \{ b_i \mid \forall \ 1\leq i \leq m \ \} \cup \{\ b_i \mid \forall \ m+1 \leq i \leq n \ \}\]

Заметим $:$

\[ \mid \ \{ b_i \mid \forall \ 1\leq i \leq m \ \} \cap [1, \dots, m+1 ] \mid = m+1-x \ \ \to \ \mid \{ b_i \mid \forall \ 1\leq i \leq m \ \} \cap [m+2, \dots, m+2015 ] \mid = x-1\]

Для больших $b_i$

\[\{\ b_i \mid \forall \ n+1 \leq i \leq n-x+2016 \ \} \subset [n+2, \dots, \ n-x+2016+2015]\]

Тогда можно выразить максимум требуемого как $:$

\[ \mathbb{(\ i\ )}( \ n\geq m+x \ ) \mid \underbrace{\max{\left ( \sum \limits_{j=m+1}^{n} b_j \right )} =\left ( \sum \limits_{j=m+x+1}^{n+1} j \right ) + \left ( \sum \limits_{j=n-x+2017}^{n+2015} j \right ) }_{\frac{(n+1)(n+2)-(m+x+1)(m+x) + (n+2015)(n+2016)-(n+2016-x)(n+2017-x)}{2}}\]

Тогда $:$

\[ _{^{( \ \star \ ) \mid \sum \limits_{j=m+1}^{n} (b_j - j-x) \leq \frac{(n+1)(n+2)-(m+x+1)(m+x) + (n+2015)(n+2016)-(n+2016-x)(n+2017-x)-n(n+1)+m(m+1)-2(n-m)x}{2}}} \]

Совершим небольшой счет $ :$

\[_{2RHS = n(n+1)+2(n+1)-m(m+1)-x(2m+1+x)+(n+2015)(n+2016)-(n+2015)(n+2016)+(x-1)(2n+4031-x) -n(n+1)+m(m+1)-2x(n-m)= 2(x-1)(2015-x)}\]

Возьмем $:$

\[ f(x) = (x-1)(2015-x) = 2016x - 2015- x^2 \ \mid \ f'(x) = 2016 - 2x\]

Максимум при $:$

\[ \mid \ f'(x) \mid = f'(x) \ \to \ \mid f'(y) \mid = - f'(y) \quad \forall \ x<y\]

Тогда $:$

\[ f'(x)=2016-2x = 2(1008-x) \ \to \max{(f(x))} = (2015-1008)(1008-1)=1007^2 \]

А минимум $:$

\[ \mathbb{(\ i\ )}( \ n\geq m+2016-x \ ) \mid \underbrace{\min{\left ( \sum \limits_{j=m+1}^{n} b_j \right )} =\left ( \sum \limits_{j=m+2}^{m-x+2016} j \right ) + \left ( \sum \limits_{j=m+2016}^{n+x} j \right ) }_{\frac{(m-x+2016)(m-x+2017)-(m+1)(m+2) + (n+x)(n+x+1) - (m+2015)(m+2016)}{2}}\]

Тогда $:$

\[ _{^{( \ \star \ ) \mid \sum \limits_{j=m+1}^{n} (b_j - j-x) \geq \frac{(m-x+2016)(m-x+2017)-(m+1)(m+2) + (n+x)(n+x+1) - (m+2015)(m+2016)-n(n+1)+m(m+1)-2(n-m)x}{2}}} \]

Совершим небольшой счет $ :$

\[_{2RHS = (m+2015)(m+2016)-(x-1)(2m+4032-x)-m(m+1)-2(m+1)+n(n+1)+x(2n+1+x)-(m+2015)(m+2016)-n(n+1)-m(m+1)-2x(n-m)=2(x-2015)(x-1)}\]

Возьмем $:$

\[ f(x) = (x-1)(x-2015) = -2016x + 2015 + x^2 \ \mid \ f'(x) = 2x-2016\]

Минимум при $:$

\[ \mid \ f'(x) \mid = -f'(x) \ \to \ \mid f'(y) \mid = f'(y) \quad \forall \ x<y\]

Тогда $:$

\[ f'(x)=2x-2016 = 2(x-1008) \ \to \min{(f(x))} = (1008-2005)(1008-1)=-1007^2 \]

Теперь другие два случая $:$

\[ \mathbb{(\ ii\ )}( \ n\leq m+x-1 \ ) \mid \max{\left ( \sum \limits_{j=m+1}^{n} (a_j-x) \right ) \leq (x-1)(2015-x) \leq 1007^2}\]

И $:$

\[\mathbb{(\ ii\ )}( \ n\leq m+2015-x \ ) \mid \min{\left ( \sum \limits_{j=m+1}^{n} (a_j-x) \right ) \geq (2015-x)(1-x) \geq -1007^2}\quad \square \]