1

Question:

Let $S$= $\{3, 7, 11, 15, 19, . . . , 95, 99, 103\} $

How many elements must be selected from the set $S$ to ensure at least two elements have a sum of 110?

Answer:

There are 14 pairs: $\{7, 103\}, \{11, 99\}, . . . \{51, 59\}, \{55\}, \{3\}$

and by the Pigeonhole principle, 15 elements must be selected to ensure that two elements have a sum of 110.

My attempt:

I am confused on why there are 14 pairs. I tried doing this question in a different way as I am not familiar with the Pigeonhole principle and got the wrong answer as shown below:

Given $S$= $\{3, 7, 11, 15, 19, . . . , 95, 99, 103\} $,

List the first few pair of elements whose sum is 110:

$\{7, 103\}, \{11, 99\}, \{15, 95\},... \{51, 59\}, \{55,55\},\{59,51\},...\{103,7\}$

  • The number on the left of each pair increases by 4, whereas the one on the right decreases by 4

  • The center is $(7+103)/2 =55$, so the pairs after the pair $\{55,55\}$ will be repeats of the ones before $\{55,55\}$ so exclude them

  • $\{55,55\}$ this pair has a sum of $110$ but is excluded too, since the elements are not unique as both are $55$, and $55$ cannot be added to any number other than itself to obtain the sum of $110$

The pairs remaining are:

$\{7, 103\}, \{11, 99\}, \{15, 95\},... \{51, 59\}$

and if you list all the pairs out there will be $12$ pairs, which is 24 elements. Exclude all the leftside numbers of each pair except $51$ and there will be 11 elements, which is incorrect.

So my question is why is my method wrong?

  • 1
    $x+y=110$ is the equation and use inclusion and exclusion formula of discrete mathematics. – Abdul Halim Apr 22 '20 at 19:47
  • Mathematician always likes to go through method for consuming low effort. – Abdul Halim Apr 22 '20 at 19:50
  • I excluded all the numbers on the left of each pair except 51 because then the sum of any pair will be greater than 110, and the last pair {51,59} has a sum of 110. So there is at least 2 elements whose sum is at least 110 –  Apr 22 '20 at 19:50
  • I don't know if I misunderstood the question, but I think my method should work when it doesn't. Why does it not work? –  Apr 22 '20 at 19:52
  • Actually my answer is 24 elements not 11 elements, so that is not even close to the answer of 14 –  Apr 22 '20 at 19:53

1 Answers1

1

Your method doesn't work, you've correctly identified that there are 12 pairs that could sum to 110. What you need to do then is identify the minimum number of elements you need to select to guarantee you have both elements of a pair. You identified that there are $\{7, 103\}, \{11, 99\}, \cdots, \{51, 59\}$ as 12 pairs, as well as $\{55\}$ and $\{3\}$ that cannot fit into any pair. Thus we have 14 sets overall. If we picked 14 elements, it could be the case that we picked $\{ 7, 11, \cdots, 51, 3, 55\}$, none of which can form a pair that sums to 110. Adding a 15th element guarantees it will be in one of those pairs, by the pigeonhole principle. The question asks: how many elements must be selected to guarantee there is any pair that sums to 110, so it doesn't matter which specific one it is.

rigged
  • 131
  • The question asks for the number of elements. So if there are 14 sets, shouldn't there be 24 elements not 14 because each pair contains 2 elements? –  Apr 22 '20 at 19:56
  • I'm very confused. The question asks for the least number of elements that have a sum of 110. {51,59} have a sum of 110, so why isn't the answer 2 elements instead, where I can exclude everything else? –  Apr 22 '20 at 20:05
  • You are looking for the worst-case, e.g. if the elements are picked at random, how many elements do you need to select to guarantee that you have a pair? – rigged Apr 22 '20 at 20:12
  • Okay but why did you include {55} and {3} in the set when they don't have any other element that will give a sum of 110 when paired? So why 14 pairs instead of 12, when you have 12 pairs that give a sum of 110 where the other 2 pairs don't –  Apr 22 '20 at 20:16
  • Actually I think I understand why you included the {55} and {3}, but how did you know that there are 14 elements when there are actually 24? –  Apr 22 '20 at 20:39
  • There are 14 sets that I am considering. 12 of those such sets are pairs, and 2 of them are singlets. So if we select 15 elements, we are guaranteed to have two elements in the same set, which by definition is a pair. – rigged Apr 22 '20 at 20:47
  • Yeah I understand that part, but since you have 12 sets/pairs along with 2 singlets which overall form 14 sets, wouldn't you have 26 elements in total not 15? Because the 12 sets contain 2 elements in each pair so that's 24 elements. Add the 2 singlets to 24 and you have 26 elements. So why did you only select 15 when there is actually 26? –  Apr 22 '20 at 20:56