$n$ is a integer larger than 1. When picking $n+1$ numbers from the set ${1, 2, \dots, 2n-1}$, you will find a pair whose sum equals $2n$

Question

I am trying to solve this problem using the pigeonhole principle. I am however, stuck on how to form boxes And thusly how to even begin.

I have tried to make the pairs {1, 2n-1}, {2, 2n-2} up to {n, n}. But since it´s up to {n, n}, one of the pairs will have the same number, meaning one of the numbers must be picked twice, is this allowed or am I missing something?

Thanks in advance.

Edit to clairfy: we have n pairs if we make the last one {n,n}. So when picking n+1, you have to choose from one of the boxes already made. So essentially, I am unsure if the second n in the last box {n,n} is also a valid choice for n+1.

Answer 1

Besides the specific number $n$, you can pair up the remaining elements in $\{1,2,\cdots,(2n-1)\}$ as follows:

$(1,2n-1)$
$(2,2n-2)$
$\cdots$
$(n-1,n+1)$.

So, you have the element $n$ and you also have $(n-1)$ other pairs of elements. This implies that if you are forced to select $(n+1)$ elements, then, after you pick the element $n$, you will be forced to select $(n)$ other elements from the $(n-1)$ pairs, listed above.

This implies, by the pigeonhole principle, that because you are being forced to select $n$ elements from the remaining $(n-1)$ pairs, you will be forced to select both elements from (at least) one of the $(n-1)$ pairs.

Because of the way that the $(n-1)$ pairs were constructed, where the sum of the elements in each pair equals $(2n)$, you will therefore be forced to select $2$ different numbers whose sum is $(2n)$.

Answer 2

You just need to patch up your reasoning a little bit.

There are two possibilities, either you picked n or not. And in both case by the pigeonhole hole principle you will have to chose a pair from your construction twice. QED

Answer 3

I'll patch up your explanation, seeing as you're not so far away from a logical answer.

I'll start by trying to make the condition "Two members of our choice of $n+1$ members from the set $\{1,\ldots,2n-1\},\ $ must sum to $2n$" fail.

From the set $\{1,\ldots,2n-1\},\ $ you can only choose one member from each of the $n$ boxes $(1,n-1),\ (2,n-2),\ \ldots,\ (n-1, n+1),\ (n). $ Since we only have $n$ boxes to choose from, and must choose $n+1$ members from these $n$ boxes, from the PHP we must choose from the same box twice, which forces us to choose two members whose sum is $2n.$