Der Legende nach geht die Welt unter, wenn ein 64-stöckiger "Turm von Hanoi" umgebaut wird. Wie lange dauert das?

a) 585 Jahre
b) 585 000 Jahre
c) 585 Millionen Jahre
d) 585 Milliarden Jahre

Antwort:

Bei Anwendung der bestmöglichen Strategie und vorausgesetzt, es wird ununterbrochen in jeder Sekunde je eine Scheibe versetzt, vergingen knapp 585 Milliarden Jahre.

Erklärung:

Der französische Mathematiker Édouard Lucas (1842-1891) erfand 1883 dieses kombinatorische Spiel, das zunächst als "Türme von Benares" später dann als "Turm von Hanoi" bekannt wurde. Dazu erzählte er folgende phantastische Geschichte:

Im Großen Tempel von Benares, unter dem Dom, der die Mitte der Welt markiert, ruht eine Messingplatte, in der drei Diamantnadeln befestigt sind, jede eine Elle hoch und so stark wie der Körper einer Biene. Bei der Erschaffung der Welt hat Gott vierundsechzig Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Messingplatte ruht und die übrigen, immer kleiner werdend, aufeinander folgen. Das ist der Turm von Brahma.

Tag und Nacht sind die Priester unablässig damit beschäftigt, den festgeschriebenen und unveränderlichen Gesetzen von Brahma folgend, die Scheiben von einer Diamantnadel auf eine andere zu setzen, wobei der oberste Priester nur jeweils eine Scheibe auf einmal umsetzen darf – und zwar so, dass sich nie eine kleinere Scheibe unter einer größeren befindet.

Sobald dereinst alle vierundsechzig Scheiben von der Nadel, auf die Gott sie bei der Erschaffung der Welt gesetzt hat, auf eine der anderen Nadeln gebracht sind, werden der Turm samt dem Tempel und allen Brahmanen zu Staub zerfallen, und die Welt wird mit einem Donnerschlag untergehen. Wieviel Zeit verbleibt der Menschheit noch?

Durch Ausprobieren lässt sich relativ leicht feststellen, dass ein Spieler sieben Züge braucht, um einen 3er Turm zu versetzen.

Die nächste Schwierigkeitsstufe besteht aus einem Turm mit vier Scheiben oder anders betrachtet: ein Turm mit drei Scheiben mit einer großen Unterlegscheibe darunter. Daher werden sieben Züge verbraucht, um den 3er Turm oben drauf umzusetzen, einer um die Unterlegscheibe zu versetzen und wieder sieben um den 3er Turm wieder oben drauf zu setzen: Macht insgesamt 15 Spielzüge.

Analog dazu braucht ein Spieler für einen 5er Turm zwei mal 15 und noch einen Spielzug und so weiter. Oder allgemein formuliert: Für einen Turm bestehend aus n Stufen, werden 2n-1 Spielzüge benötigt.

Die Anzahl der Spielzüge wächst also rasend schnell mit der Anzahl der Stufen. Die indischen Mönche bräuchten für 64 Stufen daher 18 446 744 073 709 551 615 Spielzüge. Nehmen wir ferner an, die Brahmanen versetzen ununterbrochen, Tag und Nacht, eine Scheibe in jeder Sekunde, bräuchten sie selbst dann etwa 584 942 417 400 Jahre, um ihre Aufgabe zu vollenden. Wenn man bedenkt, dass das Universum schätzungsweise 15 Milliarden Jahre und unsere Sonne sogar "nur" 5 Milliarden Jahre alt ist, brauchen wir uns – zumindest in dieser Hinsicht – keine Sorge um das Ende der Welt machen.

Weitere Informationen und Spielmöglichkeiten:
Die Türme von Hanoi