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

Considering n=5 i have $\{1,2,3,...,10\}$ .Making pairs such as $\{1,2\}$ ,$\{2,3\}$ ... total of $9$ pairs which are my holes and $6$ numbers are to be choosen which are pigeons .So one hole must have two pigeons ,i am done .Is this correct ?

In general if we have $2n$ numbers and then we have $2n-1$ holes and $n+1$ pigeons ,But for $n=3$ onwards it is valid ? There is something wrong i think

Thanks

• Question edited Jul 10 '15 at 6:11
• If we need to choose $n$ elements from $\{1,2,\cdots, mn\}$ the minimum distance will be $\dfrac{mn}n= m$ If $n+1$ elements are to be chosen, one distance has to be $m-1$ Jul 10 '15 at 6:12

Suppose that you can select $n+1$ distinct integers from $\{1,\ldots,2n\}$ in such a way that all pairs differ by at least $2$. Let the chosen integers be denoted as $x_1,\ldots, x_{n+1}$. Also, let them be arranged in increasing order. Then, one has \begin{align*} x_1\geq&\,1,\\ x_2\geq&\,x_1+2\geq 3,\\ x_3\geq&\,x_2+2\geq 5,\\ \vdots&\\ x_k\geq&\,2k-1,\\ \vdots&\\ x_{n+1}\geq&\,2(n+1)-1=2n+1>2n. \end{align*} This is a contradiction, since $x_{n+1}$ is supposed to be at most $2n$.

Well, in your case when $n=5$, you shouldn't make the pairs $\lbrace1,2\rbrace,\lbrace2,3\rbrace,...,\lbrace8,9\rbrace,\lbrace9,10\rbrace$, but rather $\lbrace1,2\rbrace,\lbrace3,4\rbrace,...,\lbrace7,8\rbrace,\lbrace9,10\rbrace$, as in the first case the same integer appears in two different pairs.

When we have the correct pairs established, we can directly apply the pigeonhole principle on our $n=5$ "holes" $\lbrace1,2\rbrace,\lbrace3,4\rbrace,...,\lbrace7,8\rbrace,\lbrace9,10\rbrace$, and we see that if we have $n+1=6$ "pigeons" in the "holes", at least one of our "holes" must contain two pigeons.

We then apply the same reasoning to the general case.

• Oh i made a blunder ! Thanks ... Jul 10 '15 at 6:27

You have nine holes and six pigeons, so the pigeonhole principle doesn't help because $6<9$.
Just use five holes $\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}$

Suppose to the contrary that there are no two consecutive numbers among the $n+1$ chosen numbers. Then there are $n$ "gaps" between the chosen numbers, with at least $1$ non-chosen number in each gap. But that would mean the total number of numbers is $\ge (n+1)+n$. This is impossible, since we only have $2n$ numbers.

• Thats a very good approach .Thanks Jul 10 '15 at 6:31
• You are welcome. Jul 10 '15 at 6:42

Suppose not, then numbers differ by at least two. Order the numbers $a_1<a_2<\dots <a_n$. Then $a_1\geq 1$. We prove $a_i\geq 1+(i-1)2$ by induction

Base step $i=1$ is clear (we have to prove $a_1\geq 1+(1-1)2+1=1$)

Inductive step. We have $a_{i}\geq 1+(i-1)2$ and $a_{i+1}\geq a_i+2$ so $a_{i+1}\geq 1+(i-1)2+2=1+((i+1)-1)2$. Taking $i=n+1$ we get $a_n\geq 1+(n+1)2=2n+1$, a contradiction since all number must be in set $\{1,2,3\dots 2n\}$

Why should there be a problem from n = 3 onwards ?

Remember there are to be 2n numbers, n pairs.

In your example, the pairs you made should be 5 pairs, {1,2}, {3,4}, ... {9,10}

We can choose max 1 # from each pair, so all the pigeon holes have been "used up" by the $n_{th}$ draw

Given the set $S=\{1,2,3,\ldots,2n\}$.We have to choose $n+1$ points from $S$,and there must be $2$ of them which are consecutive.

To apply the Pigeon-hole Principle here, clearly, there are $n+1$ "letters" so that the number of Pigeon-holes or "letter-boxes" must be $n$.

So, given $n$ boxes, there must be at least two integers amongst the $n+1$ integers which share the property that they are consecutive.

Why $n+1$ integers?What if we take $\gt n+1$ or $\lt n+1$ integers from $S$?

If we take $\gt n+1$ integers from $S$ since the conclusion holds for $n+1$, the extra numbers can be thrown for free, and the result holds good.

If we take $\lt n+1$ integers from $S$, say for example $n$, the result doesn't hold,

A simple choice for this is the set $\{1,3,5,\ldots,2n-1\}$ or the set $\{2,4,6,\ldots,2n\}$ where there are no consecutive integers.