Pigeon Hole Principle : For $n + 1$ numbers

Question

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 !

Answer 1

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