Республиканская олимпиада по математике, 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)$$ . Противоречие

Рассмотрим перестановку чисел $a_1, a_2, \dots, a_{2010}$, где $a_i$ — это числа от 1 до 2010 в произвольном порядке. После применения операции

b_i = a_i + i

получим новый набор чисел $b_1, b_2, \dots, b_{2010}$, где каждое число получается сложением исходного числа и его позиции.

Шаг 1: Границы значений $b_i$}

Минимальное значение $b_i$ достигается при $a_1 = 1$, тогда

b_1 = 1 + 1 = 2.

Максимальное значение $b_i$ достигается при $a_{2010} = 2010$, тогда

b_{2010} = 2011 + 2011 = 4022

Таким образом, все числа $b_i$ лежат в диапазоне от 2 до 4022..

Шаг 2: Проверка наличия разности 2010}

Рассмотрим множество $S$ всех значений $b_i$. По условию, все $b_i$ различны, и, следовательно, множество содержит 2010 элементов в отрезке $[2, 4020]$.

Так как отрезок $[2, 4020]$ содержит 4019 чисел, то в нем обязательно найдутся два числа $b_i$ и $b_j$, такие что:

b_j = b_i + 2010.

Что и доказывает требуемое утверждение.