Difference between revisions of "2006 USAMO Problems/Problem 2"
5849206328x (talk | contribs) m (→See Also) |
|||
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 | + | == 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}} | {{MAA Notice}} |
Revision as of 08:44, 5 August 2014
Problem
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
.
Solution
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
.
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.