Pairs summing to $2n+1$

#pigeonhole#sum#pairs

Statement

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

Hint

Pair the numbers as $(1,2n),(2,2n-1),\ldots,(n,n+1)$ .

Show solutionHide solution

Pairs. These $n$ pairs each sum to $2n+1$ .

Pigeonhole. With $n+1$ integers and $n$ pairs, some pair contains $2$ chosen integers.

Conclusion. Those two sum to $2n+1$ .