Der Turmbau von Hanoi

Da man nur eine Scheibe auf einmal bewegen darf, ist es notwendig, die unterste/größte Scheibe des Stapels auf den rechten Stab zu versetzen.

Damit dies möglich ist, muss zum einen der rechte Stab frei sein und zum anderen dürfen keine anderen Scheiben auf der größten Scheibe liegen. Wir müssen also den blauen Turm (der stellvertretend für alle Scheiben steht, die kleiner als die größte Scheibe sind) auf den mittleren Stab versetzen, die große Scheibe nach rechts setzen und dann den blauen Turm rechts auf die größte Scheibe setzen.

Der blaue Turm ist genau eine Scheibe kleiner, als der gesamte Turm. Um ihn in die Mitte zu versetzen, führen wir die drei eben beschriebenen Schritte für den kleineren Turm durch. Wir müssen also die unterste Scheibe des blauen Turmsin die Mitte versetzen und dafür alle darauf liegenden Scheiben (grüner Turm) auf den rechten Stab versetzt haben.

Um den grünen Turm zu bewegen, verfahren wir ebenfalls wie oben. Wir zerlegen auf diesem Weg die Aufgabe einen Turm zu versetzen in immer mehr Teilaufgaben, die daraus bestehen kleinere Türme zu versetzen. Sobald wir einen Turm aus nur noch einer Scheibe haben, ist es nicht mehr nötig diese Zerlegung vorzunehmen. 

Um die Lösung durchzuführen müssen wir uns nun noch überlegen, auf welchem Stab welcher der verkleinerten Türme landen muss.