What is the minimum value of X such that the following statement is always true:
Given any set of 19 distinct integers whose sum is greater than or equal to 1800, then there is a subset of X of them whose sum is greater than or equal to 900.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let's arrange the 1 9 distinct numbers in ascending order, i.e. { x 1 , x 2 , . . . , x 1 9 } where x 1 < x 2 . . . < x 1 9 .
We need to prove that if we pick the top 9 numbers and if their sum is < 9 0 0 , then the sum of all the 1 9 numbers (irrespective of the value of lower 1 0 numbers) will always be < 1 8 0 0 .
In other words, for the sum of these 1 9 numbers to be ≥ 1 8 0 0 , the sum of the top 9 should be ≥ 9 0 0
Let's choose the top 9 elements, i.e. { x 1 1 , x 1 2 , . . . , x 1 9 }
One of the many sets of 9 distinct integers that has maximum sum < 9 0 0 is { 9 5 , 9 6 , 9 7 , 9 8 , 9 9 , 1 0 0 , 1 0 1 , 1 0 2 , 1 1 1 } (sum = 8 9 9 ).
Note that there are many other sets such that the x 1 1 number is 9 5 and yet the sum is still 8 9 9 . However, x 1 1 can't be > 9 5 for the sum to be < 9 0 0 . For the purpose of this proof, we don't need to treat those other sets differently than above set. We are mainly interested in the x 1 1 number.
Any other set of 9 distinct integers is going to have only lesser sum and will yield overall (for all 1 9 numbers) lesser sum than these 9 numbers. Hence we choose these 9 numbers to proceed with our proof.
The lower 1 0 numbers can only be lesser than 9 5 . The lower 1 0 numbers with maximum sum that we can choose are { 8 5 , 8 6 , 8 7 , 8 8 , 8 9 , 9 0 , 9 1 , 9 2 , 9 3 , 9 4 } . Their sum = 8 9 5 .
Hence, if the sum of top 9 numbers of our set of 1 9 numbers is < 9 0 0 , then the sum of all 1 9 numbers will always be < 1 8 0 0 . If the sum of top 9 numbers of our set is ≥ 9 0 0 , then we anyways have the solution.
We still need to prove that X can't be less than 9 . For the given set below, the sum of all 1 9 numbers is 1805 ( ≥ 1 8 0 0 ) and yet the sum of top 8 numbers is 804 ( < 9 0 0 ).
{ 8 6 , 8 7 , 8 8 , 8 9 , 9 0 , 9 1 , 9 2 , 9 3 , 9 4 , 9 5 , 9 6 , 9 7 , 9 8 , 9 9 , 1 0 0 , 1 0 1 , 1 0 2 , 1 0 3 , 1 0 4 } .
Hence, X can't be less than 9 for the given problem statement to be always true and sum of top 9 numbers has to be ≥ 9 0 0 for the sum of 1 9 numbers to be ≥ 1 8 0 0 .