2006 USAMO Problems/Problem 2
(Dick Gibbs) For a given positive integer find, in terms of , the minimum value of for which there is a set of distinct positive integers that has sum greater than but every subset of size has sum at most .
Let one optimal set of integers be with .
The two conditions can now be rewritten as and . Subtracting, we get that , and hence . In words, the sum of the smallest numbers must exceed the sum of the largest ones.
Let . As all the numbers are distinct integers, we must have , and also .
Thus we get that , and .
As we want the second sum to be larger, clearly we must have . This simplifies to .
Hence we get that:
On the other hand, for the set the sum of the largest elements is exactly , and the sum of the entire set is , which is more than twice the sum of the largest set.
Hence the smallest possible is .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
- <url>viewtopic.php?t=84550 Discussion on AoPS/MathLinks</url>
|2006 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|