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