Turm von Hanoi

Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel, dessen Lösungsstrategie sich rekursiv entwickeln lässt. Rekursiv heißt: Hat man den ersten Fall gelöst, können alle weiteren Fälle auf den ersten zurückgeführt werden.

Um zunächst zwei Scheiben von einem Platz auf einen anderen zu transportieren, benötigt man drei Züge. Diese sehen wie folgt aus: Zuerst bewegt man die kleinere Scheibe auf einen der anderen Plätze. Dann wird die größere Scheibe auf den freien Platz gesetzt und zum Schluss die kleinere Scheibe wieder auf die größere. Hat man nun drei Scheiben, muss zunächst der Teilturm aus zwei Scheiben auf einen der freien Plätze verschoben werden. Dafür benötigt man drei Züge. Dann setzt man die größte Scheibe auf den letzten freien Platz. Schließlich muss man den Teilturm wieder auf die größte Scheibe bauen, wofür man weitere drei Züge benötigt. Es ergeben sich also insgesamt 3+1+3 = 7 Züge. Führt man alles mit vier Scheiben durch, kommt man auf 7+1+7 = 15 Schritte. Bei fünf Scheiben (wie hier in der Phänomania) sind es dann 15+1+15 = 31 Schritte, die man mindestens braucht.