1
$\begingroup$

This is a question from Shcaum's whose answer I don't understand. Our textbook has 2 pages on the pigeonhole principle and I'm having quite a bit of difficulty with it.

Give the set ${1,2,...,9}$ find how many members must be chosen to guarantee that at least one pair has a difference of 5.

There are $\binom{9}{2}=36$ possible pairs, of which exactly 4 $ \{ \{9,4\},\{8,3\},\{7,2\},\{6,1\} \} $ result in a difference of 5. They then add $\{5\}$ to the set and say there are 5 pigeonholes which requires picking a minimum of 6 numbers.

Could someone explain this?

$\endgroup$
  • $\begingroup$ I guess Shcaum's is a typo and you mean Schaum's outlines. There's plenty of book in this series, so perhaps you could be more specific, if you want to mention the book you're using. $\endgroup$ – Martin Sleziak Jan 8 '12 at 10:57
1
$\begingroup$

You can certainly pick $5$ numbers to not have the difference of $5$ ; just choose $\{ 1,2,3,4,5\}$. But you can't choose $6$, since if you consider $\{ \{1,6\}, \{2,7\}, \{3,8\}, \{4,9\}, \{5\} \}$, by the pigeonhole principle if you pick $6$ numbers out of $5$ disjoint subsets there must be one amongst which you've picked $2$ numbers, hence a pair.

Hope that helps,

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