Using the Pigeonhole Principle to show that $2$ of any $n+1$ numbers from $\{1,2,\ldots,2n\}$ sum to $2n+1$

Question

Let n be greater or to 1, and let S be an (n+1)-subset of [2n]. Prove that there exist two numbers in S whose sum is 2n+1.

I know I have to use the pigeonhole principle - no idea how to start...

Answer 1

Consider the $n$ pairs $\{1,2n\}$, $\{2,2n-1\}$, $\{3,2n-2\}$, and so on up to $\{n,n+1\}$. The two numbers in each pair add up to $2n+1$.

If we choose $n+1$ numbers, then they cannot all belong to different pairs.

You can reword this in terms of pigeons. The pair $\{1,2n\}$ are a couple, with their own pigeonhole, as are $\{2,2n-1\}$, and so on up to $\{n,n+1\}$. If there are $n+1$ pigeons currently in the pigeonholes that are their homes, then some couple must be at home.