Difference between revisions of "2006 USAMO Problems/Problem 2"
5849206328x (talk | contribs) m (→Solution) |
|||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | (''Dick Gibbs'') For a given positive integer <math>k </math> find, in terms of <math>k </math>, the minimum value of <math>N </math> for which there is a set of <math>2k+1 </math> distinct positive integers that has sum greater than <math>N </math> but every subset of size <math>k </math> has sum at most <math>N/2 </math>. | ||
− | + | == Solutions == | |
− | |||
− | == | ||
+ | === Solution 1 === | ||
Let one optimal set of integers be <math>\{a_1,\dots,a_{2k+1}\}</math> with <math>a_1 > a_2 > \cdots > a_{2k+1} > 0</math>. | Let one optimal set of integers be <math>\{a_1,\dots,a_{2k+1}\}</math> with <math>a_1 > a_2 > \cdots > a_{2k+1} > 0</math>. | ||
Line 34: | Line 34: | ||
Hence the smallest possible <math>N</math> is <math>\boxed{ N = 2k^3 + 3k^2 + 3k }</math>. | Hence the smallest possible <math>N</math> is <math>\boxed{ N = 2k^3 + 3k^2 + 3k }</math>. | ||
− | == See | + | {{alternate solutions}} |
+ | |||
+ | == See also == | ||
+ | * <url>viewtopic.php?t=84550 Discussion on AoPS/MathLinks</url> | ||
− | + | {{USAMO newbox|year=2006|num-b=1|num-a=3}} | |
− | |||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 08:48, 5 August 2014
Contents
[hide]Problem
(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 .
Solutions
Solution 1
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.
See also
- <url>viewtopic.php?t=84550 Discussion on AoPS/MathLinks</url>
2006 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.