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

$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 ?

• Note that $n$ being even is crucial. (For example, if $n=3$, then $\{1,2,5,6\}$ is a set of $n+1$ integers which doesn't have this property...) – Micah Oct 3 '15 at 20:29
• so How can I use the fact that $n$ is even here ! @Micah – alkabary Oct 3 '15 at 20:38

Why not instead consider: $$\{1,3\},\{2,4\},\{5,7\},\{6,8\},\ldots$$
• Can we generalise this pattern to $n$ where $n$ is even ? – alkabary Oct 3 '15 at 20:46