Условие
Имеется n целых чисел. Доказать, что среди них найдется несколько, или быть может одно, сумма которых делится на n.
Подсказка
Рассмотрите суммы a
1, a
1 + a
2, a
1 + a
2 + a
3, … , a
1 + a
2 + … + a
n.
Решение
Воспользуемся указанием и запишем суммы a
1, a
1 + a
2, a
1 + a
2 + a
3, … , a
1 + a
2 + … + a
n. Если одна из сумм делится без остатка на n, то задача решена. Если же ни одна сумма не делится на n, то остатки могут быть 1, 2, 3, …, n-1, т.е. всего n-1 возможностей - "клеток", а чисел у нас на единицу больше, следовательно, по крайней мере, две суммы имеют равные остатки. Осталось взять разность этих сумм.
Источники и прецеденты использования