Exercise 1108Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026
A sequence of $0$s and $1$s
#pigeonhole#sequence#blocks
Statement
Show that in any sequence of terms each equal to or , there exists a block of consecutive terms whose sum is divisible by .
Hint
Consider partial sums modulo .
Show solutionHide solution
Solution
Partial sums. Let for (with ).
Residues. Consider : that's values, but only residues mod . So two are equal: with .
Block. Then .
Conclusion. A consecutive block has sum divisible by .