Proving or Disproving the Sum in a Set

Question

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.

Thanks in advance!

Answer 1

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

Answer 2

hint

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

Answer 3

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.