Республиканская олимпиада по математике, 2010 год, 9 класс

Числа 1, 2, $\ldots,$ 2010 расположены в ряд в произвольном порядке. Рассмотрим ряд, полученный следующим образом: к каждому числу прибавляется номер его места в ряду. Докажите, что если в полученном ряду нет одинаковых чисел, то в нем найдутся два числа, разность которых равна 2010.

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

Пусть число $n$ стоит на месте $a_n$. Обозначим $c_n=n+a_n$ для всех $1\leq n\leq2010$. А также пусть $d_n$ - остаток числа $a_n$ при делении на $2010$.

Нам достаточно доказать, что найдутся два индекса $i$ и $j$ такие что $d_i=d_j$ пoскольку $0<|c_i-c_j|<2\times2010$ для всех $i$ и $j$.

Допустим что утверждение не верно и $d_i\neq d_j$. Тогда $$d_1+\dots+d_{2010}=1+2+\dots+2009=\frac{2009\times2010}{2}\equiv 1005 (mod 2010)$$. А также $c_1+c_2+\dots c_{2010}=2010\times2011\equiv 0 (mod 2010)$

Но по определению $$c_1+c_2+\dots c_{2010}\equiv d_1+d_2+\dots+d_{2010}\Longrightarrow 0\equiv 1005 (mod 2010)$$. Противоречие