2014 IMO Problems/Problem 5
For each positive integer , the Bank of Cape Town issues coins of denomination . Given a finite collection of such coins (of not necessarily different denominations) with total value at most , prove that it is possible to split this collection into or fewer groups, such that each group has total value at most .
The bound is not tight. We'll prove the result for at most with groups.
First, perform the following optimizations. - If any coin of size appears twice, then replace it with a single coin of size . - If any coin of size appears times, group it into a single group and induct downwards. Apply this operation repeatedly until it cannot be done anymore.
Now construct boxes , , ...., . In box put any coins of size (clearly there is at most one). In the other boxes , put coins of size and (at most of the former and at most one of the latter). Note that the total weight in the box is less than . Finally, place the remaining ``light coins of size at most in a pile.
Then just toss coins from the pile into the boxes arbitrarily, other than the proviso that no box should have its weight exceed . We claim this uses up all coins in the pile. Assume not, and that some coin remains in the pile when all the boxes are saturated. Then all the boxes must have at least , meaning the total amount in the boxes is strictly greater than which is a contradiction. (The inequality is strict since the pile has a coin leftover.)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|2014 IMO (Problems) • Resources
|1 • 2 • 3 • 4 • 5 • 6
|All IMO Problems and Solutions