Question

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

Answer 1

Пусть $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}$ - искомая