Die »Türme von Hanoi« findet man nicht in der Hauptstadt von Vietnam. Beziehungsweise stehen dort mit Sicherheit diverse hohe Bauwerke herum, die sind aus mathematischer Sicht jedoch uninteressant. Um die Türme von Hanoi zu finden, muss man in ein Science Center, eine mathematische Ausstellung oder einen Spielzeugladen gehen. Es handelt sich um ein Rätselspiel mit simplen Regeln, aber erstaunlicher Komplexität.

Es besteht aus drei Stäben, auf die man unterschiedlich große Scheiben mit Löchern legen kann. Dabei darf nie eine größere auf eine kleinere Scheibe gesetzt werden. Ziel des Spiels ist es, einen Turm aus nach Größe geordneten Scheiben von einem Stab auf einen anderen zu versetzen.

Die Anzahl der Scheiben variiert, doch damit es halbwegs interessant wird, sollte man mindestens drei Scheiben nehmen. Dann verschiebt man zuerst die kleinste, ganz oben auf dem Turm liegende Scheibe auf einen neuen Stab. Als Nächstes folgt die mittelgroße, die nun natürlich nicht auf die kleine gelegt werden darf, sondern auf dem letzten freien Stab abgesetzt werden muss. Dann legt man die kleine auf die mittelgroße Scheibe und macht so einen Stab frei, auf den jetzt die größte Scheibe verschoben werden kann. Die kleine Scheibe wird jetzt wieder von der mittelgroßen entfernt, die nun auf die große gelegt werden kann. Im letzten Schritt wird die kleinste Scheibe ins Ziel gebracht und der Turm vollendet.

Das waren insgesamt sieben Spielzüge, und man kann leicht zeigen, dass sich für n Scheiben bei fehlerfreiem Spiel die Anzahl der Züge bei der optimalen Lösung durch folgende Formel berechnen lässt:

Beim Spiel mit vier Scheiben steigt die Zahl der Züge schnell an. Man muss ja immer noch den Turm mit drei Scheiben aus dem vorherigen Beispiel umschichten, um die unterste Scheibe verschieben und ihn danach wieder darauf aufbauen zu können. Es braucht also doppelt so viele Züge, als bei einem um eine Scheibe kleineren Turm nötig sind, plus einen Extrazug, um die unterste Scheibe zu versetzen. Die obige Formel lässt sich damit leicht beweisen. Für n = 1, das heißt für eine Scheibe, stimmt sie offensichtlich. Und für den Schritt von n zu n + 1 kann man einfach (2ⁿ – 1) + (2ⁿ – 1) + 1 rechnen, was direkt die Behauptung bestätigt.

Warten auf den Weltuntergang

Mit steigender Anzahl der Scheiben wächst die notwendige Anzahl der Schritte bis zur Lösung, und das tut sie exponentiell. Bei fünf Scheiben sind 31 Züge nötig, bei sechs sind es 63, dann geht es mit 127, 255, 511 und 1023 Zügen weiter. Wenn man einen Zug pro Sekunde schafft, würde man bei einem optimalen Spiel mit zehn Scheiben demnach schon mehr als 17 Minuten brauchen. Bei 20 Scheiben sind es allerdings schon 1 048 575 Züge, für die man zwölf Tage durchgehendes und fehlerfreies Spiel benötigt. Bei 30 Scheiben wäre man 34 Jahre lang beschäftigt, und für ein Spiel mit 40 Scheiben sollte man knapp 35 000 Jahre einplanen.

Es hat also seine Gründe, dass die Türme von Hanoi im Spielzeugladen typischerweise mit weniger als zehn Scheiben verkauft werden. Abgesehen davon, dass man selten ein perfektes Spiel schafft, wird man normalerweise deutlich mehr als eine Sekunde Bedenkzeit pro Zug benötigen. In der Realität dauert es entsprechend sehr viel länger, bis man fertig gespielt hat, und irgendwann wird es nicht nur sehr frustrierend, sondern auch praktisch unmöglich, die Türme von Hanoi zu Ende zu spielen.

Trotz des asiatischen Namens wurde das Spiel übrigens von einem Franzosen erfunden: vom Mathematiker Édouard Lucas im Jahr 1883. Von ihm stammt auch die fiktive Geschichte, mit der es vermarktet wurde: Im Mittelpunkt der Welt, in einem Tempel in Benares, sitzen indische Mönche und arbeiten unermüdlich daran, einen Turm zu versetzen, der aus 64 goldenen Scheiben besteht. Und sobald ihnen das gelungen ist, wird die Welt enden. Die Gefahr einer nahenden Apokalypse ist folglich gering, wie alle gerne selbst nachrechnen können.