De Bank van Kaapstad

We geven een bewijs voor een veralgemening, waaruit de stelling onmiddellijk volgt: als de totale waarde niet meer is dan $n+\frac 12$, dan kunnen we de munten in $n+1$ stapeltjes of minder verdelen op zo'n manier dat elk stapeltje hoogstens waarde $1$ heeft. Dit doen we per inductie.

Inductiebegin: Voor $n=0$ kunnen we de munten gewoon op één stapel leggen, waarvan de waarde minder dan één is omdat de totale waarde van de munten hoogstens $\frac 12$ is.

Inductiehypothese: Stel dat de stelling waar is voor alle waarden die kleiner dan of gelijk zijn aan $n-1$.

Inductiestap: Stel allereerst dat er een verzameling munten met totale waarde exact één is. Door deze munten op een stapel te leggen, moeten we nu de overige munten in $n$ stapeltjes of minder verdelen waar de totale waarde hoogstens $n - \frac 12$ is, wat kan wegens de inductiehypothese. We stellen dus nu dat dit onmogelijk is; dit wilt zeggen dat er hoogstens $k-1$ munten met waarde $\frac 1k$ zijn (in het bijzonder zijn er geen met waarde $1$).

Merk nu op dat $\frac{2}{2i}=\frac 1i$. Door elke twee munten van waarde $\frac{1}{2i}$ te vervangen door één met waarde $\frac 1i$ (dit wilt zeggen, ze samen op stapeltjes leggen), kunnen we ervoor zorgen dat er hoogstens $1$ munt is met waarde $\frac{1}{2i}$. We stellen nu ook dat de totale waarde van de munten meer is dan $n-\frac 12$, anders zijn we klaar wegens de inductiehypothese.

Nu passen we op de munten die overblijven het volgende algoritme toe:

Algoritme: Bepaal de grootste munt die nog niet op een stapel ligt. Voeg deze toe aan de eerstvolgende stapel waarvoor de totale waarde na deze munt toe te voegen nog steeds kleiner is dan $1$. Indien deze niet meer bestaat, voeg je de munt toe aan een nieuwe stapel. Zo ga je verder tot alle munten op een stapel liggen.

Zij de ontstane stapels $a_1$, $a_2$, $a_3$, ..., $a_l$. We claimen nu dat $l \le n+1$. Stel, ter contradictie, dat $l>n+1$. Beschouw nu de laatste munt, zeg van waarde $\frac 1u$ die werd toegevoegd aan stapel $a_l$. Stel eerst dat $u<2n$.

Stel dat we in het algoritme op het punt staan munt (waarvan er slechts één is) $\frac{1}{2i}$ toe te voegen. Dan zal dat zeker op één van de stapels $a_1$ tot $a_i$ zijn. Immers, de waarde van de munten die hiervoor zijn toegevoegd is hoogstens $\frac 12+\frac 23+\frac 14+\frac 45+\frac 16+...+\frac {1}{2i-2}+\frac{2i-2}{2i-1}=i-1+(\frac 12-\frac 13+\frac 14-\frac 15+...-\frac{1}{2i-1}) \le i-1+\frac 12=i-\frac 12$. Als de waarde van de stapels $a_1$ tot $a_i$ echter strikt groter is dan $1-\frac {1}{2i}$ is, dan moet de totaalwaarde van de munten strikt groter zijn dan $i- \frac 12$, contradictie! Hieruit volgt dat er slechts bij een munt waarvan de omgekeerde waarde oneven is een nieuwe stapel kan toegevoegd worden. Ook dit is er hoogstens één nieuwe, omdat de totaalwaarde van alle munten van die waarde zeker minder is dan één en ze dus allemaal op een nieuwe stapel zouden kunnen. Hieruit volgt dat er na het toevoegen van munt $\frac{1}{2i-1}$ hoogstens $i$ stapels zijn. Dus na het toevoegen van munt $2n-1$ zijn er hoogstens $n$ stapels, dus is het onmogelijk dat $u<2n$.

Stel nu dus $u \ge 2n$. We weten dat voor alle stapels $a_1, a_2, ..., a_{l-1}$ de waarde strikt groter dan $\frac{u-1}{u}$ is, omdat de munt anders hier zou zijn toegevoegd. Dus zal de totaalwaarde strikt groter zijn dan $(l-1) \frac{u-1}{u}+\frac{1}{u}$, maar ze is ook kleiner dan of gelijk aan $n +\frac 12$. Dus $(n+1) \frac{u-1}{u}+\frac 1u \le (l-1) \frac{u-1}{u}+\frac 1u$<$n+\frac 12 \Rightarrow (n+1)(u-1)+1$<$un+\frac u2 \Rightarrow u-n<\frac u2 \Rightarrow u$<$2n$, contradictie! Dus $l \le n+1$. Q.E.D.