Математикадан республикалық олимпиада, 2009-2010 оқу жылы, 9 сынып
Комментарий/решение:
Пусть число n стоит на месте an. Обозначим cn=n+an для всех 1≤n≤2010. А также пусть dn - остаток числа an при делении на 2010.
Нам достаточно доказать, что найдутся два индекса i и j такие что di=dj пoскольку 0<|ci−cj|<2×2010 для всех i и j.
Допустим что утверждение не верно и di≠dj. Тогда d1+⋯+d2010=1+2+⋯+2009=2009×20102≡1005(mod2010). А также c1+c2+…c2010=2010×2011≡0(mod2010)
Но по определению c1+c2+…c2010≡d1+d2+⋯+d2010⟹0≡1005(mod2010). Противоречие
Рассмотрим перестановку чисел a1,a2,…,a2010, где ai — это числа от 1 до 2010 в произвольном порядке. После применения операции
b_i = a_i + i
получим новый набор чисел b1,b2,…,b2010, где каждое число получается сложением исходного числа и его позиции.
Шаг 1: Границы значений bi}
Минимальное значение bi достигается при a1=1, тогда
b_1 = 1 + 1 = 2.
Максимальное значение bi достигается при a2010=2010, тогда
b_{2010} = 2011 + 2011 = 4022
Таким образом, все числа bi лежат в диапазоне от 2 до 4022..
Шаг 2: Проверка наличия разности 2010}
Рассмотрим множество S всех значений bi. По условию, все bi различны, и, следовательно, множество содержит 2010 элементов в отрезке [2,4020].
Так как отрезок [2,4020] содержит 4019 чисел, то в нем обязательно найдутся два числа bi и bj, такие что:
b_j = b_i + 2010.
Что и доказывает требуемое утверждение.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.