Die Türme von Hanoi kommen in Lehrbüchern und Aufnahmeprüfungen oft als Stoff für Rekursionsformeln und vollständige Induktion in der Oberstufenmathematik vor (in Japan im Fach Mathematik B). In diesem Artikel üben wir die Gedanken an Beispielaufgaben. Die Scheiben sind von der kleinsten an mit 1, 2, 3 … nummeriert, und die Mindestzahl der Züge für einen Turm aus n Scheiben schreiben wir als aₙ.
Beispielaufgabe 1: Eine Rekursionsformel aufstellen
Aufgabe: Es gibt drei Stäbe A, B und C, und auf A liegen n verschieden große Scheiben, die größte unten. Man bewegt die Scheiben einzeln und legt nie eine große Scheibe auf eine kleinere, bis alle Scheiben auf C liegen. Schreibt man die Mindestzahl der Züge als aₙ, drücke aₙ₊₁ durch aₙ aus.
Lösung: Achte auf die größte Scheibe (Scheibe n + 1). Um sie nach C zu bewegen, müssen in diesem Moment die oberen n Scheiben alle auf B liegen.
- Die oberen n Scheiben von A nach B bewegen … mindestens aₙ Züge
- Scheibe n + 1 von A nach C bewegen … 1 Zug
- Die n Scheiben von B nach C bewegen … mindestens aₙ Züge
Mit diesem Ablauf lassen sich n + 1 Scheiben bewegen, also gilt aₙ₊₁ ≤ 2aₙ + 1. Umgekehrt fallen bei jedem Verfahren die Züge von 1 bis 3 mindestens an, also gilt aₙ₊₁ ≥ 2aₙ + 1. Daher ist
aₙ₊₁ = 2aₙ + 1 (a₁ = 1)
In Prüfungen wird manchmal verlangt, „≤“ und „≥“ beide zu zeigen und so die Gleichheit festzustellen. Eine ausführlichere Erklärung steht in der Formel für die Mindestzahl der Züge.
Beispielaufgabe 2: Das allgemeine Glied bestimmen
Aufgabe: Bestimme das allgemeine Glied der Folge, die durch a₁ = 1 und aₙ₊₁ = 2aₙ + 1 festgelegt ist.
Lösung: Eine Rekursionsformel der Form aₙ₊₁ = p·aₙ + q formt man mit einem α um, das α = 2α + 1 erfüllt. Es ist α = −1, also addierst du auf beiden Seiten 1:
aₙ₊₁ + 1 = 2(aₙ + 1)
Die Folge aₙ + 1 ist eine geometrische Folge mit dem Anfangsglied a₁ + 1 = 2 und dem Quotienten 2. Also ist aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, und
aₙ = 2ⁿ − 1
Zur Probe prüfst du, dass a₁ = 1, a₂ = 3 und a₃ = 7 zur Rekursionsformel passen.
Beispielaufgabe 3: Mit vollständiger Induktion beweisen
Aufgabe: Beweise mit vollständiger Induktion, dass die Mindestzahl der Züge für n Scheiben 2ⁿ − 1 beträgt.
Lösung:
- Für n = 1 lässt sich eine Scheibe in einem Zug bewegen und nicht in weniger, die Mindestzahl ist also 1 = 2¹ − 1, und die Aussage stimmt.
- Wir nehmen an, dass für n = k die Mindestzahl 2ᵏ − 1 beträgt. Für n = k + 1 ist die Mindestzahl nach dem Gedanken aus Beispielaufgabe 1 gleich 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, die Aussage stimmt also auch für n = k + 1.
- Aus 1 und 2 folgt, dass die Aussage für alle natürlichen Zahlen n gilt.
Entscheidend ist, dass „sowohl ≤ als auch ≥“ aus Beispielaufgabe 1 im Schritt 2 der Induktion benutzt wird.
Beispielaufgabe 4: Wenn nur Züge zum Nachbarstab erlaubt sind
Aufgabe: Die Stäbe A, B und C stehen in einer Reihe, und Scheiben dürfen nur zwischen A und B und zwischen B und C bewegt werden (von A nicht direkt nach C). Bestimme die Mindestzahl bₙ der Züge, um n Scheiben von A nach C zu bewegen.
Lösung: Die größte Scheibe n muss zweimal bewegt werden, nämlich A → B → C.
- Die oberen n − 1 Scheiben von A nach C bewegen … bₙ₋₁ Züge (um n nach B zu bewegen, muss B frei sein)
- Scheibe n von A nach B … 1 Zug
- Die n − 1 Scheiben von C nach A bewegen … bₙ₋₁ Züge (um n nach C zu bewegen, muss C frei sein)
- Scheibe n von B nach C … 1 Zug
- Die n − 1 Scheiben von A nach C bewegen … bₙ₋₁ Züge
Also ist bₙ = 3bₙ₋₁ + 2 (b₁ = 2). Aus α = 3α + 2 folgt α = −1, also bₙ + 1 = 3(bₙ₋₁ + 1). Die Folge bₙ + 1 ist eine geometrische Folge mit dem Anfangsglied 3 und dem Quotienten 3, daher
bₙ = 3ⁿ − 1
Für 1 bis 6 Scheiben haben wir mit einer Rechnung, die alle Anordnungen durchgeht, bestätigt, dass diese Zugzahl die kleinste ist. Interessanterweise durchläuft man in den 3ⁿ − 1 Zügen alle 3ⁿ Anordnungen genau einmal (die Zahl der Anordnungen steht im Artikel zu den Regelmäßigkeiten).
Beispielaufgabe 5: Übungsaufgaben
Zum Schluss darfst du selbst rechnen. Die Antworten stehen unten.
- Bestimme die Mindestzahl der Züge bei 10 Scheiben.
- Ab wie vielen Scheiben liegt die Mindestzahl der Züge über 1000?
- Wie oft bewegt sich die kleinste Scheibe, wenn man n Scheiben mit der Mindestzahl der Züge bewegt?
Antworten: 1. 2¹⁰ − 1 = 1.023 Züge. 2. Aus 2ⁿ − 1 > 1000 folgt 2ⁿ > 1001. Wegen 2⁹ = 512 und 2¹⁰ = 1024 sind es 10 Scheiben oder mehr. 3. 2ⁿ⁻¹ Mal (der Grund steht unter „Wie oft sich jede Scheibe bewegt“ im Artikel zu den Regelmäßigkeiten).
