Принцип Дирихле

Рассмотрим последовательность из 100 чисел: Построим частичные суммы:

Рассмотрим остатки от деления частичных сумм на 100. Эти остатки могут принимать значения от 0 до 99. Таким образом, у нас есть 100 остатков и 100 частичных сумм.

Если хотя бы один из остатков равен 0, то существует частичная сумма, которая делится на 100, и утверждение доказано.

Если ни один остаток не равен 0, то по принципу Дирихле среди 100 остатков, каждый из которых принимает одно из 99 возможных значений (от 1 до 99), найдутся два одинаковых остатка. Пусть это будут остатки частичных сумм и для Тогда:

что означает, что сумма делится на 100.