For each positive integer \(n\), the Bank of Cape Town issues coins of denomination \( \frac{1}{n} \). Given a finite collection of such coins (of not necessarily different denominations) with total value at most \( 99 + \frac{1}{2} \), prove that it is possible to split this collection into 100 or fewer groups, such that each group has total value at most 1.

## Comments

Sort by:

TopNewestOutline; will complete this later.

The idea is to induct. Replace the \(100\) by \(n.\) The sum doesn't exceed \(k - \dfrac{1}{2}\) and we need to show that they can be split in to \(n\) groups such that the sum of no groups exceeds \(1\). The base case is trivial; suppose the assertion is true for some \(1, 2, \cdots , k-1.\) Let \(j\) be the largest odd factor of \(k,\) and divide the numbers less than \(k\) in to \(k+1\) groups based on their largest odd divisors (all numbers with their largest odd divisors \(x\) go in group \(x\)). It is easy to show that the sum of no group exceeds \(1\). It it also easy to prove that all the coins which are smaller than \(\dfrac{1}{2k}\) fit in to these groups without the sum exceeding \(1,\) so the induction step is complete.

Log in to reply