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

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