Pigeonholes?

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.

10 8 9 11

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.

2 solutions

Pawan Kumar
Mar 22, 2015

Let's arrange the 19 19 distinct numbers in ascending order, i.e. { x 1 , x 2 , . . . , x 19 } \{x_{1}, x_{2}, ..., x_{19}\} where x 1 < x 2 . . . < x 19 x_{1} \lt x_{2} ... \lt x_{19} .

We need to prove that if we pick the top 9 9 numbers and if their sum is < 900 \lt 900 , then the sum of all the 19 19 numbers (irrespective of the value of lower 10 10 numbers) will always be < 1800 \lt 1800 .

In other words, for the sum of these 19 19 numbers to be 1800 \geq 1800 , the sum of the top 9 9 should be 900 \geq 900

Let's choose the top 9 9 elements, i.e. { x 11 , x 12 , . . . , x 19 } \{x_{11}, x_{12}, ..., x_{19}\}

One of the many sets of 9 9 distinct integers that has maximum sum < 900 \lt 900 is { 95 , 96 , 97 , 98 , 99 , 100 , 101 , 102 , 111 } \{95, 96, 97, 98, 99, 100, 101, 102, 111\} (sum = 899 = 899 ).

Note that there are many other sets such that the x 11 x_{11} number is 95 95 and yet the sum is still 899 899 . However, x 11 x_{11} can't be > 95 \gt 95 for the sum to be < 900 \lt 900 . 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 11 x_{11} number.

Any other set of 9 9 distinct integers is going to have only lesser sum and will yield overall (for all 19 19 numbers) lesser sum than these 9 9 numbers. Hence we choose these 9 9 numbers to proceed with our proof.

The lower 10 10 numbers can only be lesser than 95 95 . The lower 10 10 numbers with maximum sum that we can choose are { 85 , 86 , 87 , 88 , 89 , 90 , 91 , 92 , 93 , 94 } \{85, 86, 87, 88, 89, 90, 91, 92, 93, 94\} . Their sum = 895 = 895 .

Hence, if the sum of top 9 9 numbers of our set of 19 19 numbers is < 900 \lt 900 , then the sum of all 19 19 numbers will always be < 1800 \lt 1800 . If the sum of top 9 9 numbers of our set is 900 \geq 900 , then we anyways have the solution.

We still need to prove that X X can't be less than 9 9 . For the given set below, the sum of all 19 19 numbers is 1805 ( 1800 \geq 1800 ) and yet the sum of top 8 8 numbers is 804 ( < 900 \lt 900 ).

{ 86 , 87 , 88 , 89 , 90 , 91 , 92 , 93 , 94 , 95 , 96 , 97 , 98 , 99 , 100 , 101 , 102 , 103 , 104 } \{86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104\} .

Hence, X can't be less than 9 9 for the given problem statement to be always true and sum of top 9 9 numbers has to be 900 \geq 900 for the sum of 19 19 numbers to be 1800 \geq 1800 .

Great! The key here is to find x 10 x_{10} , and bound around that value.

Calvin Lin Staff - 6 years, 2 months ago
Vijay Katta
Mar 20, 2015

Key here is identifing critical case ; numbers are consecutive

 First number be 'n'
 19(n+9)>=1800 (1805 as 'n' is integer)

n=86

Now check whether 8 numbered subset is possible

max possible sum of 8 numbers is 804; so not possible

9 numbered set is possible as 96(next least number)+804=900

So 9 is minimal value for X.

You have only considered this for 1 case. It is not clear to me what you are doing here.

How do you know that this is the "critical case"? How do you know that in all other cases, the answer is 9?

Calvin Lin Staff - 6 years, 2 months ago

Log in to reply

There must be at least one subset with X numbers whose element sum >=900

So for this to happen with minimal X we will obviously place maximum X elements out of 19 integers

In case of consecutive integers difference between maximum X elements and other elements is minimal, as difference between each element is 1(minimum again).

Here total sum is 1800 in all other cases also but sum of maximum X elements is relatively closer to sum of other elements in case of consecutive integers; thus forms a critical case in which maximum value for X is required for summing up at least to half of total sum (900).

Hoping I am not flawed :)

vijay katta - 6 years, 2 months ago

Log in to reply

Yes, that's the general idea, but you still have to be careful with the presentation. For example, you cannot just assume that "the integers must be consecutive in the maximum X elements".

Calvin Lin Staff - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...