[Math] Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

Question

$n$ is also given to be an even number.

So I want to prove this by using the pigeon-hole principle.

I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as follows : $$\{1,2\}, \{3,4\},……,\{2n-1,2n \}$$

if $n+1$ numbers are to be chosen from these $n$ boxes, How to show that there will be remaining numbers that differ by 2 ?

Let's say we have $n=4$ then we would have
$$\{1,2\} ,\{3,4\}, \{5,6\}, \{7,8 \}$$

Now if we $5$ numbers are chosen from the above, then we want to show that there are two of the three numbers remaining that differ by $2$

Here I have $4$ holes and $5$ pigeons, so one of these pairs must be chosen when choosing the $5$ numbers , But still I can't argue that we will be left with 2 numbers that differ by 2.

ANy suggestions ?

Answer 1

Why not instead consider: $$\{1,3\},\{2,4\},\{5,7\},\{6,8\},\ldots$$

Alternately:

Pick an element from the set. Now there is at least one element that is ineligible to be picked next, as it is 2 away from the first element. Proceed by induction.