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
 A: 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$.
A: 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.
A: 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\}$
A: 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\}$
A: 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.
A: 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 
A: 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.
A: You have to choose $n+1$ integers from the set $S$ = {1, 2, 3, . . ., 2n}.
if you construct the pigeonholes as follows: {$1,2$} {$3,4$} {$5,6$} . . . { $2n-1$ , $2n$ }
we can notice that there are $n$ possible pairs, by PHP $n+1 > 1 *n$ thus there exists at least 2 integers that belong to the same pigeonhole, consequently, those two integer differ by 1.
