Задача
COM-B1-M05-P013 Общий вариант частичных сумм
#13
★★★☆☆ Уровень 3 из 5
Докажите, что среди любых \(n\) целых чисел найдётся непустой подряд идущий блок, сумма которого делится на \(n\).
Повторите доказательство с \(n\) частичными суммами.
Рассмотрим \(s_1,\ldots,s_n\). Если некоторый \(s_i\equiv0\pmod n\), то сумма первых \(i\) чисел подходит. Иначе все \(s_i\) имеют один из \(n-1\) ненулевых остатков. Две суммы имеют одинаковый остаток; их разность является суммой непустого подряд идущего блока и делится на \(n\).
Ключевая олимпиадная лемма.