Exercise 891Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Pigeonhole with integers

#pigeonhole#consecutive integers#differences

Statement

Show that among any $n+1$ integers from $\{1,\ldots,2n\}$ , two are consecutive.

Hint

Group the integers into pairs $(1,2),(3,4),\ldots,(2n-1,2n)$ .

Show solutionHide solution

Pigeonhole. There are $n$ pairs and $n+1$ chosen integers. By pigeonhole, two chosen integers fall in the same pair. Those two are consecutive.

Conclusion. Two of the chosen integers are consecutive.