# How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?

-

Just count the pairs that do add up to 16:

$$1+15 = 16, \quad3+13=16,\quad \dots$$

Then just ensure you choose enough numbers to guarantee that you have both numbers in one of these pairs.

-

Simple, choose the lowest values that add up to 16. Count how many numbers you had to pick, and you answer is at least this many.

Now look at the numbers in the list, does any pair add up to 16? In our case the answer is no, because no pair in $\{1,3,5,7\}$ adds up to 16, although the sum total is.

So, add the next number to the list, what about now? Well, we have $\{1,3,5,7,9\}$ and $7+9$ is a pair that adds up to 16. We had to choose at least 5 elements, and that's your magic number.

-
Nice. Your answer made the most sense. – joshmcode Nov 28 '15 at 19:23

Notice the number of pairs that add up to $16$ . Can you take one from each pair? Think of this similar problem: you have $4$ white sox, and $4$ blue ones. How many do you need to have a pair of the same color?

-
more like: you have 2 white socks, 2 black, 2 red, 2 blue. Not 4 white-4 blue. – Thanos Darkadakis Dec 6 '13 at 8:28
You're right, but it seemed too much of a give away. – user99680 Dec 6 '13 at 8:37

If you choose numbers $\{1,3,5,7\}$ there is no pair that add up to 16.

If you add one more then you have what you want. SO, you need at least 5.

-

You can be sure that you have extracted a couple that sums up to $16$ when you have extracted $5$ numbers. In fact, in the worst case, the first $4$ numbers you extract can not contain a couple that sums up to $16$. This means that the remaining $4$ numbers are those that can complete couples with the extracted ones. For example: $$\{1, 5, 9, 13\} \text{first 4 numbers extracted}$$ $$\{15, 11, 7, 3\} \text{the remaining 4 numbers}$$ The fifth extract surely will create a couple that sums up to $16$.

-