2016 USAJMO Problems/Problem 4
Problem
Find, with proof, the least integer such that if any elements are removed from the set , one can still find distinct numbers among the remaining elements with sum .
Solution
Since any elements are removed, suppose we remove the integers from to . Then the smallest possible sum of of the remaining elements is so clearly . We will show that works.
contain the integers from to , so pair these numbers as follows:
When we remove any integers from the set , clearly we can remove numbers from at most of the pairs above, leaving at least complete pairs. To get a sum of , simply take these pairs, all of which sum to . The sum of these elements is , as desired.
We have shown that must be at least , and that this value is attainable. Therefore our answer is .
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2016 USAJMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |