2016 USAJMO Problems/Problem 4
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 .
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 .
|2016 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|