# Pigeon Hole Principle : For $n + 1$ numbers

My question is :

• Take $n + 1$ numbers out of $1, 2,..., 2n$
• Show that there will be two consecutive numbers

My Approach :

• Using the Pigeon Hole Principle , the $n$ holes are labelled $(1, 2), (3, 4), . . ., (2n − 1, 2n)$
• A chosen number $k$ goes into hole $(j, j + 1)$ exactly if $k ∈ (j, j + 1)$

Am I correct ? Help would be appreciated !

• Using these holes, if $n+1$ numbers are picked, then by PHP, two of those numbers are bound to fall in the same hole, and then they'd be consecutive. Looks correct. – Ashish Gaurav Apr 21 '15 at 15:00
• The only missing piece, from both the problem and the answer, is that the $n+1$ chosen numbers must all be distinct. [note: without this condition you could just pick the same number $n+1$ times.] – vadim123 Apr 21 '15 at 16:06

Your argument is correct. I would however write e.g. $\color{red}{\{}1,2\color{red}{\}}$ instead of $(1,2)$.
An alternative argument: label the $n+1$ (distinct) chosen numbers as $a_1<a_2<\ldots<a_{n+1}$. If there weren't consecutive numbers then $a_{k+1}-a_k\geq 2$ for all $1\leq k\leq n$. But then $$2n\geq a_{n+1}\geq a_n+2\geq a_{n-1}+4\geq\cdots\geq a_1+2n\geq 1+2n.$$