Exercise 1816Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

A triple summing to a multiple

#pigeonhole#triple#multiple

Statement

Show that among any $2n+1$ integers, there are $n$ whose sum is divisible by $n$ .

Hint

Use the pigeonhole principle on partial sums, or an Erdős–Ginzburg–Ziv type argument.

Show solutionHide solution

Solution

Special case $n=2$ . Among $5$ integers, three have sum divisible by $3$ ? That's EGZ for $n=3$ , needing $5$ integers.

For general $n$ . EGZ theorem states: any $2n-1$ integers contain $n$ whose sum is divisible by $n$ . This is a deep theorem (Erdős–Ginzburg–Ziv), proved via the Cauchy–Davenport theorem.

Conclusion. EGZ theorem: $2n-1$ integers contain $n$ summing to a multiple of $n$ .

A triple summing to a multiple

Statement

Solution

More problems in Pigeonhole principle