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.

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!

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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
1  
@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.

share|improve this answer
    
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.

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.