Türme von Hanoi
Die Türme von Hanoi sind ein klassisches mathematisches Rätsel. Drei Stäbe, ein Stapel Scheiben unterschiedlicher Größe und zwei strenge Regeln: Bewegen Sie immer nur eine Scheibe, und legen Sie nie eine größere auf eine kleinere.
Drei Stäbe und ein Kegel aus Scheiben
Das Brett hat drei Stäbe. Die Scheiben sind alle unterschiedlich groß und lassen sich auf die Stäbe schieben. Zu Beginn liegt der ganze Satz auf einem Stab, nach Größe sortiert, die größte unten und die kleinste oben, sodass der Stapel ein Kegel ist. Ziel ist es, den ganzen Turm auf einen anderen Stab zu bringen.
Die drei Regeln
1. Bewegen Sie immer nur eine Scheibe. 2. Ein Zug nimmt die oberste Scheibe eines Stapels und legt sie auf einen anderen Stapel oder auf einen leeren Stab. 3. Eine größere Scheibe darf nie auf einer kleineren liegen. Diese drei Regeln sind das ganze Spiel. Mit ihnen ist jede erlaubte Stellung eine Aufteilung der Scheiben auf die Stäbe, bei der jeder Stab sortiert bleibt.
Die kürzeste Lösung ist 2ⁿ − 1
Die wenigsten Züge, mit denen sich ein Turm aus n Scheiben lösen lässt, sind 2ⁿ − 1. Eine Scheibe braucht 1 Zug. Zwei Scheiben brauchen 3. Drei brauchen 7, vier 15 und fünf 31. Jede neue Scheibe verdoppelt die vorige Lösung und fügt den einen Zug hinzu, der die größte Scheibe trägt: Brauchen n − 1 Scheiben T Züge, dann brauchen n Scheiben 2T + 1. Diese Rekursion ergibt genau 2ⁿ − 1. Acht Scheiben, der größte Turm in der PictorX-App, brauchen 255 Züge. Einen kürzeren erlaubten Weg gibt es nicht.
So funktioniert die Rekursion
Um n Scheiben vom Startstab zum Zielstab zu bringen, mit dem übrigen Stab als Hilfsstab: 1. Bringen Sie die oberen n − 1 Scheiben vom Startstab auf den Hilfsstab. 2. Bringen Sie die größte Scheibe vom Startstab direkt auf den Zielstab. 3. Bringen Sie die n − 1 Scheiben vom Hilfsstab auf den Zielstab, auf die größte Scheibe. Schritt 2 ist erlaubt, weil die größte Scheibe auf jedem Stab liegen darf. Die Schritte 1 und 3 sind dasselbe Rätsel, eine Scheibe kleiner. Der Aufruf endet bei einer einzelnen Scheibe, die einmal bewegt wird. Entfaltet ergibt das die 2ⁿ − 1 Züge, und kein Schritt legt je eine größere Scheibe auf eine kleinere.
Die Legende der 64 goldenen Scheiben
Der französische Mathematiker Édouard Lucas stellte das Rätsel 1883 vor. Dazu erzählte er eine Legende über einen indischen Tempel in Kashi Vishwanath, in dem Priester nach genau diesen Regeln einen Stapel aus 64 goldenen Scheiben versetzen. Wenn der letzte Zug getan ist, so die Legende, geht die Welt unter. Vierundsechzig Scheiben brauchen 2⁶⁴ − 1 Züge: 18.446.744.073.709.551.615. Bei einem fehlerfreien Zug pro Sekunde, Tag und Nacht, sind das etwa 585 Milliarden Jahre. Die Priester werden nicht fertig.
In PictorX spielen
Öffnen Sie die Türme von Hanoi, und auf dem Startstab steht bereits ein Turm aus vier Scheiben. Fünfzehn Züge sind das Minimum. Ziehen Sie die oberste Scheibe auf einen anderen Stab, oder klicken Sie auf einen Stab und dann auf den gewünschten. Die Tasten 1, 2 und 3 tun dasselbe. Eine größere Scheibe auf einer kleineren wird abgelehnt. Scheiben reicht von 1 bis 8, sodass Sie 1, 3, 7, 15, 31, 63, 127 und 255 mit der Formel vergleichen können. Schritt spielt einen Zug einer kürzesten Lösung ab. Lösen spielt den Rest ab. „3 Scheiben ansehen“ zeigt die rekursive Strategie in Bewegung. Rückgängig und Wiederholen gehen Ihre Züge durch. Speichern Sie ein PNG, oder öffnen Sie das Brett im PictorX-Editor.
Häufig gestellte Fragen
Was sind die Regeln der Türme von Hanoi?
Bewegen Sie immer nur eine Scheibe. Nehmen Sie die oberste Scheibe eines Stabs und legen Sie sie auf einen anderen Stab. Legen Sie nie eine größere Scheibe auf eine kleinere. Der ganze Turm beginnt auf einem Stab und muss auf einem anderen enden.
Wie viele Züge braucht die kürzeste Lösung?
2ⁿ − 1. Eine Scheibe braucht 1 Zug, zwei Scheiben 3, drei 7, vier 15 und fünf 31. Jede weitere Scheibe verdoppelt die vorige Lösung und fügt einen Zug hinzu.
Wer hat die Türme von Hanoi erfunden?
Der französische Mathematiker Édouard Lucas stellte es 1883 vor. Die Geschichte von Priestern und 64 goldenen Scheiben in Kashi Vishwanath ist die Legende, die er dem Rätsel mitgab.
Wie lange würden 64 Scheiben dauern?
2⁶⁴ − 1 Züge, also 18.446.744.073.709.551.615. Bei einem Zug pro Sekunde sind das etwa 585 Milliarden Jahre.
Verwandte Tools
Türme von Hanoi
Versetzen Sie im Browser einen Turm aus Scheiben über drei Stäbe. Immer nur eine Scheibe, nie eine größere auf eine kleinere. Die kürzeste Lösung hat 2ⁿ − 1 Züge.
Buffons Nadel
Lassen Sie im Browser Nadeln auf einen Boden mit Linien fallen. Zählen Sie die Kreuzungen und sehen Sie zu, wie Buffons Experiment von 1777 π schätzt.
Buffons Nadel
Buffons Nadelproblem von 1777: warum eine auf parallele Linien fallende Nadel π schätzt, wie die Wahrscheinlichkeit 2l/(πd) für die kurze Nadel aus der Fläche unter einer Sinuskurve entsteht und warum das Experiment nur langsam konvergiert.
Multiplikationskreise
Verbinden Sie jede Zahl auf einem Kreis mit ihrem Vielfachen. Zeichnen Sie eine Einmaleinsreihe, eine Kardioide oder ein Fadenbild auf Papier, mit Kreide oder auf Holz.
Die Collatz-Vermutung
Erkunden Sie das Collatz-3n+1-Problem im Browser. Verfolgen Sie Hagelkorn-Folgen, lassen Sie einen geometrischen Collatz-Baum wachsen und zoomen Sie in das kontinuierliche Collatz-Fraktal.
Langtons Ameise
Starten Sie Langtons Ameise im Browser. Sehen Sie Symmetrie, Chaos und die 104-Schritte-Autobahn, und probieren Sie dann mehrfarbige Regeln, mehrere Ameisen, ein Sechseckgitter und Turmiten.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Türme von Hanoi spielen