Hemmes mathematische Rätsel: Die Türme von Hanoi – wie sieht die Lösung dieses Spiels aus?
Der französische Mathematiker Édouard Lucas wurde 1842 in Amiens geboren und starb 1891 in Paris. Er schrieb das vierbändige Werk »Recréations Mathématiques«, das zwischen 1883 und 1894 erschien und zu einem Klassiker der Unterhaltungsmathematik wurde. 1883 brachte er unter dem Pseudonym »N. Claus de Siam«, einem Anagramm von »Lucas d’Amiens«, ein Solitärspiel auf den Markt, das er »Die Türme von Hanoi« nannte. Er behauptete, das Spiel sei eine vereinfachte Version des Turms von Brahma. Indische Mönche müssten im großen Tempel von Benares einen Turm aus 64 goldenen Scheiben versetzen. Bevor ihnen das gelänge, wäre aber der Tempel zu Staub zerfallen und mit einem Donnerschlag das Ende der Welt gekommen. »Die Türme von Hanoi« bestehen aus einem Brettchen, auf dem drei gleiche zylindrische Stäbe montiert sind. Auf dem linken Stab stecken fünf verschieden große, mittig durchbohrte Scheiben. Sie sind der Größe nach geordnet, wobei die größte Scheibe unten liegt. Ziel des Spiels ist es, mit möglichst wenigen Zügen alle Scheiben vom linken Stab auf den rechten Stab zu bringen. Mit einem Zug darf immer nur eine Scheibe von einem Stab genommen und auf einen anderen Stab gesteckt werden. Dabei darf niemals eine größere Scheibe auf eine kleinere Scheibe gelegt werden. Wie viele und welche Züge sind für den Scheibentransport notwendig?
Wir ersetzen die Scheiben der Größe nach durch Zahlen. Nun bauen wir die Lösung systematisch auf und beginnen darum mit einem Turm mit nur einer Scheibe (oberes Bild). Die Lösung ist trivial. Mit einem Zug setzt man die Eins von links nach rechts. Bei einem Turm mit zwei Scheiben (mittleres Bild) setzt man erst die Eins von links in die Mitte, dann die Zwei von links nach rechts und zum Schluss die Eins von der Mitte nach rechts. Man braucht also 3 = 22 – 1 Züge. Bei einem Turm mit drei Scheiben (unteres Bild) lassen wir in Gedanken erst einmal die Drei fort. Dadurch reduziert sich das Problem auf die Aufgabe mit nur zwei Scheiben, die wir nun mit drei Zügen von links in die Mitte transportieren. Mit einem vierten Zug setzen wir anschließend die Drei von links nach rechts. Nun lassen wir im Gedanken erneut die Drei fort und transportieren wieder mit drei Zügen die zwei Scheiben von der Mitte nach rechts. Insgesamt sind dies also 3 + 1 + 3 = 7 = 23 – 1 Züge. Das Problem des Turms mit vier Scheiben können wir ganz analog auf das des Turms mit drei Scheiben zurückführen. Man benötigt folglich 7 + 1 + 7 = 15 = 24 – 1 Züge. Für den Turm mit fünf Scheiben sind schließlich 15 + 1 + 15 = 31 = 25 – 1 Züge notwendig. Allgemein benötigt man für einen Turm mit n Scheiben 2n – 1 Züge. Das Originalspiel von Édouard Lucas hatte übrigens acht Scheiben.
Schreiben Sie uns!
1 Beitrag anzeigen