Maths WorkshopMaths problems with full solutions
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 n+1n+1 terms each equal to 00 or 11, there exists a block of consecutive terms whose sum is divisible by nn.

Hint

Consider partial sums modulo nn.

Show solutionHide solution

Solution

Partial sums. Let Sk=a1+⋯+akS_k = a_1+\cdots+a_k for k=1,…,n+1k=1,\ldots,n+1 (with S0=0S_0=0).

Residues. Consider S0,S1,…,Sn+1S_0,S_1,\ldots,S_{n+1}: that's n+2n+2 values, but only nn residues mod nn. So two are equal: Si≡Sj(modn)S_i\equiv S_j\pmod n with i<ji<j.

Block. Then ai+1+⋯+aj=Sj−Si≡0(modn)a_{i+1}+\cdots+a_j = S_j-S_i\equiv 0\pmod n.

Conclusion. A consecutive block has sum divisible by nn.