Exercise 1628Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Sum via pigeonhole

#pigeonhole#sums#olympiad

Statement

Show that among any $n+1$ integers from $\{1,\ldots,2n\}$ , some two have sum $2n+1$ .

Hint

Pair the elements as $(1,2n),(2,2n-1),\ldots,(n,n+1)$ . These are $n$ pairs; each pair sums to $2n+1$ .

Show solutionHide solution

Pigeonhole. Among $n+1$ chosen integers from $n$ pairs, two come from the same pair.

Sum. Any two in the same pair sum to $2n+1$ .

Conclusion. Two of the chosen integers sum to $2n+1$ .