Exercise 1814Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

A subset with sum divisible by $n$

#pigeonhole#subset sum#divisibility

Statement

Given $n$ integers, show that some nonempty subset has sum divisible by $n$ .

Hint

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

Show solutionHide solution

Solution

Partial sums. $S_1,\ldots,S_n$ : $n$ values, $n$ residues.

Case 1: some $S_k\equiv0$ . That subset $\{a_1,\ldots,a_k\}$ works.

Case 2: no $S_k\equiv0$ . Then $n$ values in $n-1$ nonzero residues: two equal, say $S_i=S_j$ ( $i<j$ ). Then $a_{i+1}+\cdots+a_j\equiv0\pmod n$ .

Conclusion. A nonempty subset has sum divisible by $n$ .

A subset with sum divisible by $n$

Statement

Solution

More problems in Pigeonhole principle