Der Erfinder des Schachspiels wünscht sich der Legende nach folgenden Lohn: ein Reiskorn auf das erste Feld des Bretts, zwei auf das zweite, vier auf das dritte – auf jedem Feld doppelt so viele wie auf dem vorigen.
Wie viele Körner liegen am Ende auf den 64 Feldern? Gib eine geschlossene Formel an.
Addiere die ersten Felder von Hand: $1, 3, 7, 15, \dots$ – wie verhält sich jede dieser Summen zur nächsten Zweierpotenz?
Die Lösung ist ausgeblendet. Nimm dir erst selbst Zeit für die Aufgabe – der Aha-Moment lässt sich nicht nachholen.
Hast du es ernsthaft versucht – und den Hinweis gelesen? Danach gibt es kein Zurück im Kopf.
Lösung
Auf Feld $k$ liegen $2^{k-1}$ Körner. Gesucht ist also
Geschlossene Form. Der übliche Teleskoptrick: Multipliziere $S$ mit 2 und ziehe $S$ wieder ab. Alle mittleren Terme heben sich auf:
Also $S = 2^{64} - 1$, allgemein $\sum_{k=0}^{n-1} 2^{k} = 2^{n} - 1$.
Die Zahl.
Was das bedeutet. Bei etwa 25 Milligramm pro Reiskorn sind das rund $4{,}6 \cdot 10^{11}$ Tonnen – gut 460 Milliarden Tonnen. Die Weltreisernte liegt bei etwa 520 Millionen Tonnen im Jahr; man müsste also rund 900 Jahre lang die gesamte Welternte abliefern. $\blacksquare$
Bemerkenswert ist die Verteilung: Auf dem letzten Feld allein liegen $2^{63}$ Körner, also mehr als auf allen 63 Feldern davor zusammen – deren Summe ist $2^{63} - 1$. Die erste Bretthälfte bringt es auf lediglich $2^{32} - 1 \approx 4{,}3$ Milliarden Körner, etwa 100 Tonnen. Alles Wesentliche passiert am Schluss; das ist die eigentliche Pointe exponentiellen Wachstums.