Among $n+1$ from $2n$, two consecutive

#pigeonhole#consecutive#betweenness

Statement

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

Hint

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

Show solutionHide solution

Pairs. $n$ pairs $(2k-1,2k)$ for $k=1,\ldots,n$ .

Pigeonhole. $n+1$ integers in $n$ pairs: some pair has $2$ .

Conclusion. Two are consecutive.