4
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ashish Gaurav Apr 21 '15 at 15:00
  • $\begingroup$ 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.] $\endgroup$ – vadim123 Apr 21 '15 at 16:06
4
$\begingroup$

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

$\endgroup$

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.