Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Martin Sleziak Jan 8 '12 at 10:57

1 Answer 1

up vote 1 down vote accepted

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.