Задача 97855

Темы:    [ Принцип Дирихле (прочее) ] [ Деление с остатком ] [ Сочетания и размещения ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Курляндчик Л.Д.

Набор чисел  A₁, A₂, ..., A₁₀₀  получен некоторой перестановкой из чисел 1, 2, ..., 100. Образуют сто чисел:
      B₁ = A₁,  B₂ = A₁ + A₂,  B₃ = A₁ + A₂ + A₃,  ...,  B₁₀₀ = A₁ + A₂ + A₃ + ... + A₁₀₀.
Докажите, что среди остатков от деления на 100 чисел  B₁, B₂, ..., B₁₀₀  найдутся 11 различных.

Решение

Пусть различных остатков не более десяти:  r₁, r₂, ..., r₁₀.  Расcмотрим множество S, состоящее из всевозможных попарных разностей  r_i – r_j  (i ≠ j)  и нуля. Количество элементов множества S не превышает 91. С другой стороны, для всех k  (2 ≤ k ≤ 100)  A_k = B_k – B_k–1 ≡ s (mod 100)  для некоторого s S, то есть S содержит числа, сравнимые по модулю 100 со всеми числами от 1 до 100 за исключением, возможно, A₁. Таким образом, S содержит не менее 99 чисел. Противоречие.

Замечания

10 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1984/1985
Номер	6
вариант
Вариант	осенний тур, основной вариант, 9-10 класс
Задача
Номер	2