# Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2.

In my attempt.

I try $n=2$, and so we have $\{1,2,3,4\}$ and we could partition $\{1,2,3,4\}$ into two boxes with $2$ numbers in each as follows $\{1,3 \}$ and $\{2,4 \}$. Now these two boxes are my pigeon-holes and I want to take $n+1=3$ numbers from these two boxes and so by the pigeon-hole principle, I have to take one of the two boxes that have two integers that differ by 2 and hence done.

Now I want to generalise this for any $n=2k$, How can I do it.

I thought about proceeding by induction.

Assume this works for $n=2k$ now I want to show that it works for $n=2(k+1)$.

Assume that it works for $\{1,2,.....,4k \}$, I want to show that it works for $\{1,2,.....,4k + 4 \}$

So because it works for $$\{1,2,.....,4k \}$$

This means that if $n+1 = 2k +1$ integers are chosen from

$$\{1,2,.....,4k \}$$

then there are always two integers that differ by 2.

Now considering $\{1,2,.....,4k + 4 \}$

The difference between $\{1,2,.....,4k + 4\}$ and $\{1,2,.....,4k \}$

Is just 4 numbers $$\{4k+1,4k+2,4k+3,4k+4 \}$$

Now if we want to choose $n+1 = 2k +3$. Then I stop here, And don't know how to proceed .

Any suggestions ? or is there another way to answer this question without mathematical induction !

Your induction proof can be made simpler. You already proved the base case. Now suppose you choose $m+1$ numbers from a set of size $2m$ where $m=n+2$. Let $s$ be the smallest number chosen. If $s+2$ has also been chosen you are done. If not, consider the set $\{s+k, ...,2m\}$ where $k=1$ or $k=2$, whichever makes the set have even cardinality. Since this is less than or equal to $2n$, by the induction hypothesis, there must be two numbers that are two apart.

• Ok, I just lost you for a second there. So I first assume that it works for some even $n$ and Now I want to show it works for $n+2=m$. And I consider the set $\{1,2,....2m \}$ right. Then I let $s$ bet the smallest number chosen from this set, and then if $s+2$ has been chosen also, I am done. If not, I consider the set $\{s+k,.....,2m \}$ which is a subset from $\{1,,,,2m \}$. Now Why is this less than or equal to $2n$ I don't get it ? – alkabary Oct 4 '15 at 23:38
• The smallest $s$ can be is 1. If that is the case $\{s+2,..,2m\}$ is smaller by 2 which makes it less than or equal to $2n$. – John Douma Oct 4 '15 at 23:41

Divide the $4k+4$ numbers into group A = $\{1,...,4k\}$ and group B=$\{4k+1,...,4k+4\}$. I want to pick as many numbers as possible without any two numbers that differ by $2$.
You have shown that I can pick at most two from group B. It's the same argument as your main paragraph.
By the inductive hypothesis, I can pick at most $2k$ from group A.
So altogether I can pick at most $2k+2$ numbers without two that differ by $2$.
In other words, if I pick $2k+3$, I will have two that differ by $2$.

• Why did you say that there at most $2k$ chosen numbers from $1 \to 4k$ ?? – alkabary Oct 4 '15 at 23:20
• If there are more than $2k$, then there are at least $2k+1$, and your previous case handles that. So now you only have to prove when there are fewer than $2k+1$ from $1\to4k$. – Empy2 Oct 4 '15 at 23:35
• I don't really understand. I need to show that if $2k +3$ numbers are chosen from $\{1,2,....,4k+4 \}$ then there are two integers that differ by $2$. And in my induction hypothesis , I assume that if $2k +1$ numbers are chosen from $\{1,2,........,4k \}$ then there two numbers that differ by $2$. – alkabary Oct 4 '15 at 23:42