Find the minimum number of elements that one needs to take from a set $$ S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$ to be sure that there exists at least 2 numbers with the sum of 10.

Here are my work so far:

These are the pairs with the sum of 10: (1, 9), (2, 8), (3, 7), (4, 6)

If we select 4 numbers, then at least 2 of them must be in the same pairs above. But then the set also contains 5, so I suppose that we need at least 5 numbers to safely have a pair with a sum of 10 - is this correct?

  • $\begingroup$ Alright select $\{1,2,3,4,5\}$. Where's the pair that adds up to $10$? $\endgroup$ – AgentS Nov 4 '19 at 5:21
  • $\begingroup$ If you select four then you don't have to have at least to from the same pair. (Why did you say they did.) All four can be from different pairs. Or three can be from different pairs and one can be $5$. And if you choose five then it could be that one is a $5$ and the other four are all from different pairs. But if you choose six then can they all be from different pairs or not from a pair? At most one is $5$ and the remaining five must come from the pairs. They can't all come from different pairs because there are only four pairs. So at least two must come from the same pair. $\endgroup$ – fleablood Nov 4 '19 at 5:27
  • $\begingroup$ "If we select 4 numbers, then at least 2 of them must be in the same pairs above." Why? what if I pick $1,8, 3$ and $6$. Or if I pick $1,8,5,$ and $7$. You have the right idea but you are making strange claims. $\endgroup$ – fleablood Nov 4 '19 at 5:29
  • $\begingroup$ Oh true! If I pick 4 numbers from S, they won't be necessarily in the same pair. Your example of 1, 8, 3, and 6 just proved it. So at least I will need to pick 5 numbers so 2 out of those numbers will be in the same pair. $\endgroup$ – Steve Franchise Nov 4 '19 at 5:33
  • $\begingroup$ Then we also see that we have the element 5 in S that does not belong to any pair, so that forces us to pick one more number to be on the safe side. So in total, I will need at least 6 numbers to have at least 2 numbers with a sum of 10. Is this correct? $\endgroup$ – Steve Franchise Nov 4 '19 at 5:34

If we take $6$ of them then there will be at least one pair giving a sum of $10$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.