Rätsel und Codes
Türme von Hanoi
Auch: Turm von Hanoi, Tower of Hanoi
Kurz erklärt
Die Türme von Hanoi sind ein Denkspiel, bei dem ein Turm aus Scheiben einzeln auf einen anderen Stab umgesetzt wird, nie eine größere auf eine kleinere.
Das Spiel besteht aus drei Stäben und mehreren gelochten Scheiben verschiedener Größe. Zu Beginn stecken alle Scheiben der Größe nach auf dem ersten Stab, die größte unten. Ziel ist, den ganzen Turm auf einen anderen Stab zu bringen. Dabei gelten zwei Regeln: Man darf immer nur eine Scheibe bewegen, und nie darf eine größere auf einer kleineren liegen.
Herkunft
Der französische Mathematiker Édouard Lucas stellte das Spiel 1883 vor, unter einem Decknamen, der ein Anagramm seines eigenen Namens war. Dazu erfand oder übernahm er eine Legende: In einem Tempel versetzten Mönche einen Turm aus 64 goldenen Scheiben, und wenn sie fertig seien, gehe die Welt unter.
Wie viele Züge es braucht
Für n Scheiben braucht man mindestens 2ⁿ − 1 Züge:
- 1 Scheibe: 1 Zug
- 2 Scheiben: 3 Züge
- 3 Scheiben: 7 Züge
- 4 Scheiben: 15 Züge
Der Grund ist rekursiv: Um die unterste Scheibe zu bewegen, muss zuerst der ganze Turm darüber weg, dann wandert die große Scheibe, dann kommt der kleinere Turm wieder obenauf. Bei 64 Scheiben wären das 18.446.744.073.709.551.615 Züge – die Mönche hätten bei einem Zug pro Sekunde viele Milliarden Jahre zu tun.
Lösung mit drei Scheiben
Stäbe A, B, C, Scheiben 1 (klein) bis 3 (groß): 1 nach C, 2 nach B, 1 nach B, 3 nach C, 1 nach A, 2 nach C, 1 nach C. Sieben Züge, der Turm steht auf C.
Im Rätsel
In Escape Games sind die Türme von Hanoi ein Geduldsrätsel zum Anfassen. Oft löst erst der fertige Turm auf dem richtigen Stab einen Kontakt aus und öffnet das nächste Fach.
