Problem 5

For each positive integer

n

, the Bank of Cape Town issues coins of denomination

\tfrac{1}{n}

. Given a finite collection of such coins (of not necessarily different denominations) with total value at most

99+\tfrac12

, prove that it is possible to split this collection into

100

or fewer groups, such that each group has total value at most

1

Step 1 of 6: Two lossless merging moves

Previous step Next step

\underbrace{\tfrac{1}{2m}+\tfrac{1}{2m}}_{2} = \tfrac{1}{m}, \qquad \underbrace{\tfrac{1}{2m+1}+\cdots+\tfrac{1}{2m+1}}_{2m+1} = 1

Detailed analysis

Repeat the following two operations while possible, without changing the total value: if a coin of value $\tfrac{1}{2m}$ appears twice, replace the pair by a single coin of value $\tfrac{1}{m}$ ; if a coin of value $\tfrac{1}{2m+1}$ appears $2m+1$ times, remove all $2m+1$ of them and set them aside as their own complete group (of total value exactly $1$ ). Each operation strictly decreases the number of coins, so the process terminates.