Erarbeitung - Anzahl der Züge
Zur Orientierung
Ziel ist es jetzt, die (minimale) Anzahl $a_n$ von Zügen (das sind die Scheibenbewegungen) zu bestimmen, die man beim Umschichten eines $n$-Scheiben-Turm benötigt.
| Zustand vorher | Zustand nachher |
|---|---|
|
|
Wir beginnen mit einer Beschreibung des Umschichtverfahrens.
Das Umschichtverfahren beschreiben
Dir ist sicherlich Folgendes aufgefallen:
- Es ist ganz einfach, einen 1-Scheiben-Turm umzuschichten.
- Wenn man einen 1-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 2-Scheiben-Turm umzuschichten.
- Wenn man einen 2-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 3-Scheiben-Turm umzuschichten.
- Wenn man einen 3-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 4-Scheiben-Turm umzuschichten.
- Wenn man einen 4-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 5-Scheiben-Turm umzuschichten.
- ...
Die folgende Übersicht verdeutlicht dieses Rückführungsverfahren für einen 5-Scheiben-Turm.
|
|
|
| Bewege einen 5-Scheiben-Turm zum Endstapel | Bewege einen 4-Scheiben-Turm zum Hilfsstapel |
|
|
| Bewege 1 Scheibe zum Endstapel | |
|
|
| Bewege einen 4-Scheiben-Turm zum Endstapel | |
|
|
|
Aufgabe 1
Erläutere das Rückführungsverfahren am Beispiel Umschichtung eines 5-Scheiben-Turms
.
Die Anzahl der Züge bestimmen
Wir richten den Fokus jetzt auf die Anzahl der Züge.
Aufgabe 2
(a) Beginne mit den einfachsten Fällen: Umschichtung eines 1-ScheibenTurms und Umschichtung eines 2-Scheiben-Turms. Bestimme die zugehörigen Zuganzahlen $a_1$ und $a_2$. Diese Werte kann man sofort angeben.
(b) Bestimme anschließend $a_3$. Dazu musst du wissen, wie man einen 3-Scheiben-Turm umschichtet.
(c) Bestimme auch $a_4$. Nutze die Strategie zur Lösung des Umschichtungsproblems.
Hilfe - Umschichtung eines 4-Scheiben-Turms
|
|
|
Bewege einen 4-Scheiben-Turm zum Endstapel Anzahl der Züge: ... |
Bewege einen 3-Scheiben-Turm zum Hilfsstapel Anzahl der Züge: ... |
|
|
|
Bewege 1 Scheibe zum Endstapel Anzahl der Züge: 1 |
|
|
|
|
Bewege einen 3-Scheiben-Turm zum Endstapel Anzahl der Züge: ... |
|
|
|
(d) Bestimme analog $a_5$. Notiere die Zahlenfolge $a_1; a_2; a_3; a_4; a_5; ...$.
(e) Fällt dir bei der Zahlenfolge $a_1; a_2; a_3; a_4; a_5; ...$ eine Gesetzmäßigkeit auf? Nutze sie, um $a_{64}$ zu bestimmen.
(f) Die Mönche von Benares benötigen zum Transport von 1 Scheibe 1 Minute. Wie lange brauchen sie, um einen 64-Scheiben-Turm umzuschichten? Vergleiche diese Zeit mit dem Alter des Universums, das ca. 13.8 Milliarden Jahre beträgt. Wann ist demnach der Weltuntergang zu befürchten?
