Bei n Scheiben ist die Mindestzahl der Züge, um den Turm auf einen anderen Stab zu bewegen, 2ⁿ − 1. Das ist 2, so oft mit sich selbst multipliziert, wie es Scheiben gibt, minus 1.

ScheibenzahlMindestzahl der Züge
1 Scheibe1
2 Scheiben3
3 Scheiben7
4 Scheiben15
5 Scheiben31
6 Scheiben63
7 Scheiben127
8 Scheiben255
9 Scheiben511

Mit jeder zusätzlichen Scheibe verdoppelt sich die Zahl der Züge ungefähr. Sehen wir uns Schritt für Schritt an, warum.

Auf die größte Scheibe achten

Wir wollen einen Turm aus n Scheiben von links nach rechts bewegen. Die größte Scheibe liegt unter allen anderen und lässt sich so nicht bewegen. Um sie nach rechts zu bringen, muss in diesem Moment Folgendes gelten:

  • Auf der größten Scheibe liegt nichts.
  • Der rechte Stab ist frei (weil eine kleinere Scheibe nicht unter die größte gelegt werden darf).

Die übrigen n − 1 Scheiben müssen also alle auf dem mittleren Stab liegen.

Die Züge in drei Teile aufteilen

Von hier aus lässt sich das Bewegen von n Scheiben in drei Teile aufteilen.

  1. Die oberen n − 1 Scheiben von links in die Mitte bewegen.
  2. Die größte Scheibe in einem Zug von links nach rechts bewegen.
  3. Die n − 1 Scheiben aus der Mitte auf die größte Scheibe bewegen.

Schritt 1 und 3 sind beide genau das Problem „einen Turm aus n − 1 Scheiben bewegen“. Schreibt man die Mindestzahl der Züge für n Scheiben als T(n), ergibt sich

T(n) = T(n − 1) + 1 + T(n − 1) = 2 × T(n − 1) + 1

Bei einer Scheibe ist es ein Zug, also T(1) = 1. Daraus erhält man der Reihe nach 3, 7, 15, 31 …

Warum die Formel 2ⁿ − 1 ist

Addiert man auf beiden Seiten dieser Beziehung 1, erhält man

T(n) + 1 = 2 × (T(n − 1) + 1)

Das heißt: „Die Zahl der Züge plus 1“ verdoppelt sich mit jeder zusätzlichen Scheibe genau. Bei einer Scheibe ist T(1) + 1 = 2, bei n Scheiben ist es also 2, n-mal mit sich selbst multipliziert, also 2ⁿ. Zieht man davon 1 ab, erhält man T(n) = 2ⁿ − 1.

Warum es nicht weniger geht

Wir wissen jetzt, dass sich der Turm mit der obigen Zugfolge in 2ⁿ − 1 Zügen bewegen lässt. Gibt es aber nicht doch ein Verfahren mit weniger Zügen?

Wie oben gesagt: In dem Moment, in dem die größte Scheibe zum ersten Mal bewegt wird, müssen die übrigen n − 1 Scheiben alle auf einem anderen Stab liegen. Bis dahin braucht man mindestens so viele Züge, wie es kostet, einen Turm aus n − 1 Scheiben zu bewegen. Ebenso braucht man, nachdem die größte Scheibe zuletzt nach rechts gelegt wurde, mindestens so viele Züge wie für einen Turm aus n − 1 Scheiben, um die übrigen wieder daraufzulegen. Die größte Scheibe selbst bewegt man mindestens einmal.

Diese drei Anteile braucht jedes Verfahren. Deshalb geht es nicht mit weniger als 2 × T(n − 1) + 1 Zügen. Man weiß sogar, dass es für die Zugfolge mit den wenigsten Zügen nur diesen einen Weg gibt.

Der „Klassik“-Modus der App hat 127 Züge

Der Modus „Klassik“ der App „Türme von Hanoi“ hat 7 Scheiben, also ist die Mindestzahl der Züge 2⁷ − 1 = 127. Wenn du bei 127 Zügen angekommen bist, hast du es mit der Mindestzahl gelöst. Wenn du so spielst, wie im Artikel zur Spielweise beschrieben („die kleine Scheibe immer in dieselbe Richtung drehen“), bist du genau mit 127 Zügen fertig.