2
$\begingroup$

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 !

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – alkabary Oct 4 '15 at 23:38
  • 1
    $\begingroup$ 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$. $\endgroup$ – John Douma Oct 4 '15 at 23:41
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why did you say that there at most $2k$ chosen numbers from $1 \to 4k$ ?? $\endgroup$ – alkabary Oct 4 '15 at 23:20
  • $\begingroup$ 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$. $\endgroup$ – Empy2 Oct 4 '15 at 23:35
  • $\begingroup$ 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$. $\endgroup$ – alkabary Oct 4 '15 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.