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 2 of 6: Bounded leftover counts at every denomination

Previous step Next step

\text{after termination: } \le 1 \text{ coin of value } \tfrac{1}{2m},\quad \le 2m \text{ coins of value } \tfrac{1}{2m+1}

Detailed analysis

When no more merges are possible, for each $m$ there is at most one coin of value $1/(2m)$ and at most $2m$ coins of value $1/(2m+1)$ . Keep each complete value- $1$ group aside and let $g$ be their number. The remaining total value is at most $99\tfrac12-g=(100-g)-\tfrac12$ .