# Proving or Disproving the Sum in a Set

I am doing review questions for an exam and I am completely stumped on this particular question:

Let A = {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32}. Prove or disprove that if I select 10 distinct elements from the set A, that there are at least two pairs of elements whose sum will be exactly 34.

I can explain it logically because it makes sense that if you select any 10 numbers that there will be two or more pairs of elements whose sum will be exactly 34. I was able to prove it through example but I can use help by proving it using a different method.

-

You want the pigeonhole principle. Note that if $n$ is selected, $34-n$ cannot be. Note that this divides the set into $8$ pairs. So you must have picked both elements of two pairs.

Added: Look at your set this way. It has all the elements in the first two columns. $$\begin {array}{r r r} a&b&sum\\2&32&34\\4&30&34\\6&28&34\\8&26&34\\ &\ldots \\16&18&34 \end {array}$$

If you take two elements from the same row, you get two elements that add to $34$. There are only eight rows in the table. So if you take ten elements you will have to take two pairs (at least) that add to $34$.

-
Thanks for the reply! Can you elaborate on the 34-n cannot be because I am having a hard time understanding it. Thanks! – pyramid Apr 8 '13 at 22:52
@pyramid: Just like clark's solution. That is how he came up with his pairing. If you select $2$, you can't select $34-2=32$ and avoid a pair summing to $34$. Once you have selected $8$ elements, if you don't have a pair summing to $34$, the next two will complete two pairs. – Ross Millikan Apr 8 '13 at 23:01
I don't know if I'm completely dumb or something but it still hasn't clicked. Is there another way you can explain it? Thank you so much for all the time and effort I really appreciate it! – pyramid Apr 8 '13 at 23:23

hint

Make $8$ pairs in the following way $\{2,32\}, \{4,30\} \ldots \{16,18\}$ and use pigeonhole principle.

-
I guess you meant $\{4,30\}$? – Lord Soth Apr 8 '13 at 22:35
@LordSoth Yes, Thanks! I will fix that – clark Apr 8 '13 at 22:37

Imagine trying to select elements without any pair of them summing to $34$. For each number $n$ that you select, you must then avoid it's complementary number $34 - n$, which is also in the set. In the best case, you can choose $8$ numbers, and then on the $9$th, the sum of $34$ is inevitable.

This is an example of the Pigeonhole Principle.

-