доказать, что из любых ста целых чисел можно выбрать несколько( или,быть может, одно), сумма которых кратна 99

1

Ответы и объяснения

2013-02-16T16:45:43+04:00

Это Проверенный ответ

×
Проверенные ответы содержат надёжную, заслуживающую доверия информацию, оценённую командой экспертов. На "Знаниях" вы найдёте миллионы ответов, правильность которых подтвердили активные участники сообщества, но Проверенные ответы - это лучшие из лучших.

Пусть x_1, ..., x_{100} - данные числа. Рассмотрим суммы S_1=x_1; S_2=x_1+x_2; ...;S_{100}=x_1+x_2+...x_{100}. Если хотя бы одна из этих сумм делится на 99, задача решена. Если нет, то эти 100 сумм при делении на 99 могут давать остатки 1,2,3,...., 98 (98 разных остатков). По принципу Дирихле какие-то две суммы S_i и S_j будут давать одинаковые остатки. Предположим, что i>j, и тогда S_i-S_j=x_{j+1}+x_{j+2}+...x_{i} делится на 99. Сумма x_{j+1}+x_{j+2}+...x_{i} - искомая