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 5 of 6: An averaging argument always finds room

Previous step Next step

\text{each box has slack }\ge\tfrac1{2r}>\tfrac1{2r+1}

Detailed analysis

Insert the pile coins one at a time. If the next coin could fit in no box, every box would have value greater than $1-1/(2r+1)$ , so their total would exceed $r-r/(2r+1)$ . But the remaining total is at most $r-1/2$ , and $r-r/(2r+1)>r-1/2$ , a contradiction. Hence every pile coin fits while keeping each box at most $1$ .