Exercise 601Combinatorics › Pigeonhole principleM1Added 4 Nov 2026

A block of consecutive terms divisible by n

#pigeonhole#prefix sums#remainders

Statement

Let $a_1,a_2,\dots,a_n$ be integers. Prove that there exist $i\le j$ such that the sum $a_i+a_{i+1}+\dots+a_j$ is divisible by $n$ .

Hint

Consider the $n+1$ partial sums $S_0=0$ , $S_1=a_1$ , $S_2=a_1+a_2$ , $\dots$ , $S_n$ and their remainders modulo $n$ .

Show solutionHide solution

Solution

Idea. A block sum is a difference of two partial sums.

Pigeonhole. The $n+1$ numbers $S_0,S_1,\dots,S_n$ have only $n$ possible remainders modulo $n$ , so two of them, say $S_p$ and $S_q$ with $p<q$ , have the same remainder. Then $n$ divides
$S_q-S_p=a_{p+1}+a_{p+2}+\dots+a_q.$
Taking $i=p+1$ and $j=q$ gives the required block.

Remark. The result is sharp: for $n-1$ numbers it fails. Take $a_1=\dots=a_{n-1}=1$ .

Lesson. Turn sums of blocks into differences of prefix sums, then apply the pigeonhole principle to remainders.

A block of consecutive terms divisible by n

Statement

Solution

More problems in Pigeonhole principle