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 most , prove that it is possible to split this collection into or fewer groups, such that each group has total value at most

Proof:

Replace by . I will prove the stronger statement that we can do this when the coins have total value at most .

We perform induction on . Note that the base case of is trivial. Now, if we have two or more coins with value for some then we can make two of them into a coin with value and apply the induction hypothesis. We can do the same if we have or more coins with value . Therefore assume we have at most coins with value and at most coin with value for any .

Clearly we can assume there are no coins with value . Place all the coins with value into a box (there is clearly at most such coin). For every positive integer , put all coins with value or into a box (clearly this works as the maximum value in a specfic box is then ).

Now, we have at most boxes and the only coins remaining are those with value or less. I claim we can distribute these coins among the already-created boxes. Assume the contrary - then the total value of coins in each box is more than so the total value of all coins is greater than , contradiction! Therefore, we are done.