2014 IMO Problems/Problem 5
Problem
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 
.
Solution
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
![\[k \left( 1 - \frac{1}{2k+1} \right)\]](http://latex.artofproblemsolving.com/e/a/1/ea1731218840b32c7ab24f111d07b47df85c0c96.png)
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.
See Also
| 2014 IMO (Problems) • Resources | ||
| Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
| All IMO Problems and Solutions | ||
