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 3 of 6: Pack the surviving large coins into boxes

B_0,\ldots,B_{99}

Previous step Next step

r:=100-g,\quad B_0,\dots,B_{r-1}

Detailed analysis

Put the at-most-one coin of value $1/2$ into $B_0$ . For each $m=1,\dots,r-1$ , put at most $2m$ coins of value $1/(2m+1)$ and at most one coin of value $1/(2m+2)$ into $B_m$ . Its value is at most $2m/(2m+1)+1/(2m+2)<1$ . Here $r=100-g$ , so these boxes and the $g$ complete groups will total $100$ groups.