2
$\begingroup$

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two.

Clearly this is an application of the pigeonhole principle. However, I'm not sure how to write up a coherent proof.

$\endgroup$
2
$\begingroup$

Consider the following sets: $$\{1, 3\}, \{2, 4\}, \{5, 7\}, \{6, 8\}, \{9, 11\}, \{10, 12\}, \{13, 15\}, \{14, 16\}, \{17, 19\}, \{18, 20\}$$

Together, these $10$ sets account for all of the integers $\{1, \ldots, 20\}$. When we pick 11 numbers, by the Pigeonhole Principle, we will pick both numbers from at least one of the sets. Hence, these two numbers (which we can denote $a$ and $b$) will differ by two.

Hope this helps. Cheers!

$\endgroup$
  • 1
    $\begingroup$ That makes a lot of sense. Thanks! $\endgroup$ – user111503 Nov 26 '13 at 8:07

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.