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.

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.

Here's my 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?

share|improve this question
    
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 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 at 7:46

2 Answers 2

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$.

share|improve this answer

HINT:

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

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.