Exercise 1101Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

Modular pigeonhole

#pigeonhole#modular#addition

Statement

Let $a_1,\ldots,a_n$ be integers. Show that some consecutive block $a_i+\cdots+a_j$ is divisible by $n$ .

Hint

Consider partial sums mod $n$ .

Show solutionHide solution

Partial sums. $S_k=a_1+\cdots+a_k$ for $k=1,\ldots,n$ .

Pigeonhole. Consider $S_0=0, S_1, \ldots, S_n$ : $n+1$ values in $n$ residues. Two equal: $S_i\equiv S_j$ with $i<j$ .

Block. $a_{i+1}+\cdots+a_j=S_j-S_i\equiv0\pmod n$ .

Conclusion. A consecutive block has sum divisible by $n$ .