Lösung Türme von Hanoi

Für die Lösung der Aufgabe beginnt man mit kleinen n und betrachtet dann immer eine Scheibe mehr.
Es bietet sich z. B. an, mit \(N(n)\) die Anzahl der optimalerweise benötigten Züge für eine Pyramide der Höhe \(n\) zu bezeichnen.

\(N(1)=1\): triviales Problem
\(N(2)=3\): Die kleine Scheibe wird auf 2 gelegt, die große auf 3 und dann die kleine auf 3.
\(N(3)=7\): 1→3; 1→2; 3→2; 1→3; 2→1; 2→3; 1→3
\(N(4)=15\): 1→2; 1→3; 2→3; 1→2; 3→1; 3→2; 1→2; 1→3; 2→3; 2→1; 3→1; 2→3; 1→2; 1→3; 2→3

Nach einigen \(n\) sieht man:

• Für einen Turm mit \(n\) Etagen wird zunächst analog vorgegangen wie für \(n-1\) Etagen, mit dem Unterschied, dass der Turm abzüglich der untersten Etage auf Stab 2 verschoben wird und nicht auf Stab 3. Hierfür benötigt man so viele Züge wie für den Fall \(n-1\).
• Im Anschluss wird die unterste Scheibe von 1 nach 3 bewegt, was einen weiteren Zug benötigt.
• Zuletzt wird der zuvor nach 2 verschobene Turm der Höhe \(n-1\) auf die Scheibe auf Stab 3 verschoben. Hierfür benötigt man abermals so viele Züge wie für den Fall \(n-1\)

Es gilt also offenbar \(N(1)=1\) und \(N(n)=2⋅N(n-1)+1\)

Man sieht: \( N(n) = 2^n – 1 \)