# Question about the Pigeonhole Principle

The question is:

Let $A = \{1,2,3,4,5,6,7,8\}$. If five integers are selected from $A$, must at least one pair of the integers have a sum of $9$?

The book explains the solution by dividing the number into $4$ disjoint subsets and pointing out that if the numbers in each set are added together, they result in a sum of $9$: $\{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}$.

Thus, if you pick $5$ numbers, you will inevitably find a pair, whose sum will equal to $9$.

I don't get it. When the book asks to select $5$ numbers from $A$, I can pick $\{1,2,3,4,5\}$. Then from there, I can pick two integers like $1$ and $2$, whose sum does not equal to $9$. What am I not getting here?

Thanks for any help.

-
its saying when you pick any 5 elements, you have some pair in that set of 5 elements whose sum is 9. In the set of 5 elements you picked, $4+5 = 9$ – Deven Ware Dec 15 '11 at 2:05
Of course some pairs, indeed many pairs, will not have sum $9$. But in your example, $4+5=9$. – André Nicolas Dec 15 '11 at 2:06

In that group of 5 you selected, the pair 4 and 5 sum to 9. Obviously, not all pairs from that set of 5 elements will sum to 9, the problem just asks if there must be at least one that does.

-

Let's play a game:

First, you pick five numbers from among $\{1,2,3,4,5,6,7,8\}$.

Then I get to pick two of the five numbers you picked. If I pick two that add up to $9$, then I win; if the two I pick don't add up to $9$, then you win.

What the problem says is that I can always win, no matter which five numbers you pick during your turn.

In other words, you get to pick the five numbers, but you don't also get to specify which two you want to add up to 9.

-