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
18 Mal
24 Mal
32 Mal
41 Mal
Summe15 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.

ZugBinärsystemNullen am EndeBewegte Scheibe
1101
21012
31101
410023
510101
611012
711101
8100034

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“.

ReihenfolgeGray-CodeGeänderte Stelle (von rechts)
0000―
10011
20112
30101
41103
51111
61012
71001

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.

ScheibenzahlAnordnungen
3 Scheiben27
5 Scheiben243
7 Scheiben2.187
9 Scheiben19.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.