Loading [MathJax]/jax/output/SVG/jax.js

Математикадан республикалық олимпиада, 2009-2010 оқу жылы, 9 сынып


1,2,,2010 сандары бір қатарға жазылған. Келесі жаңа қатарды қарастырайық: әр санға оның қатардағы нөмірін қосайық. Егер пайда болған жаңа қатардағы сандар әртүрлі болса, олардың ішінен айырмасы 2010-ға тең екі сан табылатынын дәлелдеңдер.
посмотреть в олимпиаде

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

пред. Правка 4   12
2 года 6 месяца назад #

Пусть число n стоит на месте an. Обозначим cn=n+an для всех 1n2010. А также пусть dn - остаток числа an при делении на 2010.

Нам достаточно доказать, что найдутся два индекса i и j такие что di=dj пoскольку 0<|cicj|<2×2010 для всех i и j.

Допустим что утверждение не верно и didj. Тогда d1++d2010=1+2++2009=2009×201021005(mod2010). А также c1+c2+c2010=2010×20110(mod2010)

Но по определению c1+c2+c2010d1+d2++d201001005(mod2010). Противоречие

  0
2 месяца назад #

Рассмотрим перестановку чисел 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.

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