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?

  • 0
    I guess Shcaum's is a typo and you mean [Schaum's outlines](http://en.wikipedia.org/wiki/Schaum%27s_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.2012-01-08

1 Answers 1

1

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,