0

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?

Matti P.
  • 6,012
Steve Franchise
  • 25
  • Alright select ${1,2,3,4,5}$. Where's the pair that adds up to $10$? – AgentS Nov 04 '19 at 05:21
  • 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. – fleablood Nov 04 '19 at 05:27
  • "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. – fleablood Nov 04 '19 at 05:29
  • 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. – Steve Franchise Nov 04 '19 at 05:33
  • 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? – Steve Franchise Nov 04 '19 at 05:34

1 Answers1

1

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

Kishalay Sarkar
  • 3,467