2014 IMO SL #N3

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

How On God's Green Earth Is This Number Theory? 

We generalize this for $k, k-\frac{1}{2}$ instead of $100, 99+\frac{1}{2}$. We present the steps to show the desired. First of all, put all coins with value $1$ into their own group, and then combine every two coins with value $\frac{1}{2m}$ into $\frac{1}{m}$, and lastly, whenever there are at least $x$ coins of value $\frac{1}{x}$, keep making groups of $1$ out of them until we can't anymore. Hence, we can WLOG let there be at most $2m-2$ coins of $\frac{1}{2m-1}$ and at most one coin of $\frac{1}{2m}$, for each $m$. Now, make $k$ groups, and for each $m\in [1, k]$, put all the coins of $\frac{1}{2m}$ and $\frac{1}{2m-1}$ in group $m$. This won't overfill any groups because $\frac{1}{2m}+\frac{2m-2}{2m-1}<1$. After this, the only coins left are $\frac{1}{2k+1}$ and smaller. But note that since the groups right now sum to at most $k-\frac{1}{2}$, so there exists a group with total value at maximum $\frac{1}{N}\left(N-\frac{1}{2}\right)$. This implies the total waste is at least $\frac{1}{2}$, meaning there is a group with waste at least $\frac{1}{2k}$ and we can take a leftover coin and put it in that group. But the total waste will never go below $\frac{1}{2}$, so we can keep repeating what we just did until all the coins are placed in a group, and thus we are done. $\square$