# Selecting from $\{1,2,3,4,5,6,7,8,9\}$ to guarantee at least one pair adds to $10$

How many numbers must be selected from the set $\{1,2,3,4,5,6,7,8,9\}$ to guarantee that at least one pair of these numbers add up to $10$? Justify your answer.

Consider the two sets $\{1,2,3,4\}$ and $\{6,7,8,9\}$. In the worst case, one may pick the number $5$ and then all the numbers from one set and then a number from the other set. Therefore, $6$ numbers must be selected in order to guarantee that at least one pair of these numbers add up to $10$.

Do you think my answer is correct?

-
Yes,now generalize it to other values.Given the numbers ${1,2,3. . .n}$, how many numbers should you pick to guarantee that a pair adds up to $n+1$ ? – rah4927 Apr 21 '14 at 7:44
Yes. Set $\left\{ 1,2,3,4,5,6,7,8,9\right\}$ is partitioned by the $5$ sets $\left\{ 1,9\right\}$, $\left\{ 2,8\right\}$, $\left\{ 3,7\right\}$, $\left\{ 4,6\right\}$, $\left\{ 5\right\}$. If $6$ numbers are picked out, then it is guaranteed that from one of these sets two distinct elements are picked out. – drhab Apr 21 '14 at 7:46

The argument is not fully persuasive, since conceivably we might pick, in addition to $5$, $3$ elements from one of our $4$-element sets and $2$ from another, and not get a sum of $10$. This actually can't happen, but there are more cases to look at than the ones you have studied.

Consider instead the following. Divide our collection of numbers as follows:

$$\{5\},\quad \{1,9\},\quad \{2,8\},\quad \{3,7\},\quad \{4,6\}.$$

Suppose we choose $6$ numbers. Then since there are only $4$ "pigeonholes" in the collection $\{1,9\}, \{2,9\}, \{3,7\}, \{4,6\}$, we must have chosen at least $2$ numbers from the same pigeonhole, that is, two numbers with sum $10$. And it is clear that we can pick $5$ numbers in several ways so that the sum of no two is $10$.

-

HINT:

If you want to add exactly to 10. Divide into pairs where sum is 10. Then apply Pigeonhole principle.

-