Given 9 natural numbers 1,2,3,4 .... 8,9. How many numbers must be put out to make sure there exist two numbers with a total of 10?

1 Answer
George C.
Aug 14, 2018

Six

Explanation:

If I understand the question correctly, we want to know the minimum size for a subset #S# of #{1,2,3,4,5,6,7,8,9}# which will force there to exist two elements of #S# with sum #10#.

Note that #5# elements is not sufficient, since the subset #{1,2,3,4,5}# has no two elements whose sum is #10#.

On the other hand, note that we can partition #{1,2,3,4,5,6,7,8,9}# into #5# subsets:

#{1, 9}#, #{2, 8}#, #{3, 7}#, #{4, 6}#, #{5}#

Then if #S sube { 1, 2, 3, 4, 5, 6, 7, 8, 9 }# has at least #6# elements, it must include two elements from one of the subsets in the partition, but then it contains two elements whose sum is #10#.

Related questions
Impact of this question
1269 views around the world
You can reuse this answer
Creative Commons License