Löst man die Türme von Hanoi mit der Mindestzahl der Züge, zeigt die Zugfolge erstaunlich schöne Regelmäßigkeiten. Hier stelle ich der Reihe nach vor, was man bei der Zugfolge mit den wenigsten Zügen (2ⁿ − 1 Züge) für einen Turm aus n Scheiben von links nach rechts findet. Die Scheiben sind von der kleinsten an mit 1, 2, 3 … nummeriert.
Wie oft sich jede Scheibe bewegt, ist eine Zweierpotenz
In der Zugfolge mit den wenigsten Zügen steht fest, wie oft sich jede Scheibe bewegt. Bei n Scheiben bewegt sich Scheibe k 2ⁿ⁻ᵏ Mal.
| Scheibe (bei 4 Scheiben) | Anzahl der Bewegungen |
|---|---|
| 1 | 8 Mal |
| 2 | 4 Mal |
| 3 | 2 Mal |
| 4 | 1 Mal |
| Summe | 15 Mal |
Die größte Scheibe bewegt sich 1 Mal, die nächste 2 Mal, die nächste 4 Mal und so weiter: Mit jeder kleineren Scheibe verdoppelt es sich. Die Summe ist 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 und stimmt genau mit der Mindestzahl der Züge überein.
Der Grund folgt aus demselben Gedanken wie in der Formel für die Mindestzahl der Züge. Um n Scheiben zu bewegen, bewegt man einen Turm aus n − 1 Scheiben zweimal. Deshalb bewegen sich die Scheiben, die kleiner als Scheibe n sind, doppelt so oft wie beim Bewegen von n − 1 Scheiben.
Welche Scheibe in welchem Zug bewegt wird
Schreibt man bei 4 Scheiben in der Zugfolge mit den wenigsten Zügen die Nummern der bewegten Scheiben vom ersten Zug an auf, erhält man:
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Die 1 kommt in jedem zweiten Zug vor, dazwischen jede zweite Stelle eine 2, dazwischen wieder eine 3 und so weiter. Das hat dieselbe Form wie die Längen der Striche auf einem Lineal (kurz, mittel, kurz, lang …).
Diese Folge lässt sich sofort bestimmen, wenn man die Zugnummer im Binärsystem schreibt.
| Zug | Binärsystem | Nullen am Ende | Bewegte Scheibe |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 10 | 1 | 2 |
| 3 | 11 | 0 | 1 |
| 4 | 100 | 2 | 3 |
| 5 | 101 | 0 | 1 |
| 6 | 110 | 1 | 2 |
| 7 | 111 | 0 | 1 |
| 8 | 1000 | 3 | 4 |
In Zug m wird die Scheibe mit der Nummer „Anzahl der Nullen am Ende von m im Binärsystem + 1“ bewegt. Bei ungeraden Zügen endet die Binärzahl auf 1, also wird immer die 1 bewegt. Das ist der Grund für „bei ungeraden Zügen bewegst du die 1“ im Artikel zur Lösungsmethode.
Auch den Ausgangs- und den Zielstab kann man allein mit Rechnungen im Binärsystem bestimmen (Artikel zum Algorithmus).
Der Zusammenhang mit dem Gray-Code
Zählt man im Binärsystem von 0 an hoch, ändert sich bei jedem Schritt eine unterschiedliche Zahl von Stellen (von 0111 zu 1000 ändern sich 4 Stellen). Eine Darstellung der Zahlen, bei der sich bei jedem Schritt nur eine Stelle ändert, nennt man „Gray-Code“.
| Reihenfolge | Gray-Code | Geänderte Stelle (von rechts) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
Die Folge der geänderten Stellen „1 2 1 3 1 2 1“ ist genau dieselbe wie die Folge der bewegten Scheiben bei den Türmen von Hanoi. Sieht man jede Scheibe als eine Stelle im Binärsystem und denkt „wenn sich diese Stelle ändert, bewegt sich diese Scheibe“, dann ist die Zugfolge mit den wenigsten Zügen dasselbe wie das Durchlaufen des Gray-Codes.
Die Drehrichtung der Scheiben
Im Artikel zur Lösungsmethode steht, dass sich die 1 immer in dieselbe Richtung dreht. Tatsächlich gilt dieselbe Regel auch für die anderen Scheiben.
- Scheiben mit ungerader Nummer (1, 3, 5 …) drehen sich alle in dieselbe Richtung wie die 1.
- Scheiben mit gerader Nummer (2, 4, 6 …) drehen sich alle in die Gegenrichtung der 1.
Wenn der linke Turm nach rechts soll, geht die 1 bei ungerader Scheibenzahl in der Richtung „links → rechts → Mitte“, bei gerader Scheibenzahl in der Richtung „links → Mitte → rechts“. Keine Scheibe ändert ihre Richtung bis zum Ende ein einziges Mal.
Es gibt noch eine weitere Regel, die im Artikel 10 Scheiben lösen vorkommt: In der Zugfolge mit den wenigsten Zügen liegt nie eine ungerade Scheibe direkt auf einer ungeraden und nie eine gerade direkt auf einer geraden.
Es gibt insgesamt 3ⁿ Anordnungen
Wie viele regelkonforme Anordnungen der Scheiben gibt es insgesamt? Jede Scheibe kann auf einem der drei Stäbe liegen, und die Reihenfolge der Scheiben auf einem Stab ist durch die Größe festgelegt. Es gibt also 3ⁿ Anordnungen.
| Scheibenzahl | Anordnungen |
|---|---|
| 3 Scheiben | 27 |
| 5 Scheiben | 243 |
| 7 Scheiben | 2.187 |
| 9 Scheiben | 19.683 |
Außerdem lässt sich von jeder Anordnung aus jede andere Anordnung nach den Regeln erreichen. Stellt man alle Anordnungen als Punkte dar und verbindet Punkte, die mit einem Zug erreichbar sind, durch Linien, entsteht eine Figur, die dem „Sierpinski-Dreieck“ sehr ähnlich ist, in der kleine Dreiecke in einem großen Dreieck ineinander verschachtelt sind.
Der Modus „Rätsel“ der App „Türme von Hanoi“ bildet seine Aufgaben, bei denen ein Vorbild nachzubauen ist, aus all diesen Anordnungen. Selbst bei ★5 mit 9 Scheiben werden die Aufgaben erst gestellt, nachdem die kürzeste Zugzahl für alle 19.683 Anordnungen bestimmt wurde.
