Um n Scheiben zu bewegen, müssen Sie zuerst die oberen n − 1 wegräumen, dann die größte Scheibe einmal bewegen und anschließend jene n − 1 wieder darauflegen. Also gilt M(n) = 2M(n − 1) + 1 mit M(1) = 1, und das löst sich zu 2ⁿ − 1: Acht Scheiben brauchen 255 Züge und drei brauchen 7, in den ersten beiden Links. 255 kommt jedem bekannt vor, der Speichergrößen liest – es ist der größte Wert, den ein vorzeichenloses Byte fasst, und zwar aus genau diesem Grund.
Lucas' Version kam mit vierundsechzig goldenen Scheiben und einer Prophezeiung, die Welt werde enden, wenn der Stapel umgeschichtet sei. Bei einem Zug pro Sekunde sind das 2⁶⁴ − 1 = 1.844674407371⋅10+19 Züge (dritter Link), etwa 585 Milliarden Jahre, mehr als das Vierzigfache des Weltalters – und das Acht-Scheiben-Puzzle vor Ihnen dauert anderthalb Minuten. Dieselbe Verdopplung, die den kleinen Fall trivial macht, macht den großen geologisch, und das ist der ganze Sinn einer Exponentialfunktion: 255 und 1.844674407371⋅10+19 sind dieselbe Regel, sechzig Schritte auseinander.
Antwort
255
So lesen Sie sie
2⁸ − 1 auf der Rechenfläche. Der zweite Link sind drei Scheiben; der dritte ist die Zählung der vierundsechzig Scheiben, die die Welt beendet.
Quelle
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.