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 6 of 6: Conclusion for k = 100

Previous step Next step

\#\{\text{groups}\} \le k = 100

Detailed analysis

There are $g$ complete groups of value $1$ and $r=100-g$ boxes, each of value at most $1$ . Their total number is $g+r=100$ , proving the required partition.