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?
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,