Anzahl der Züge

Die minimale Anzahl der Bewegungen bestimmen

Wir betrachten das Umschichtungsproblem jetzt aus einer anderen Perspektive.

Zustand vorher:

Zustand nachher:

Aufgabe 1

(a) Beginne mit den einfachsten Fällen. Bestimme $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 im letzten Abschnitt entwickelte Strategie zur Lösung des Umschichtungsproblems.

Eine Zahlenfolge beim Problemlösen nutzen

Wenn man die minimalen Anzahlen von Bewegungen $a_1;a_2;a_3;a_4;a_5;...$ zum Umschichten eines $n$-Scheiben-Turmes systematisch bestimmt, dann ergibt sich diese Zahlenfolge:

$1;3;7;15;31;...$

Aufgabe 2

(a) Vielleicht ist dir auch schon folgende Gesetzmäßigkeit aufgefallen:

$a_2=2\cdot a_1+1$
$a_3=2\cdot a_2+1$
$a_4=2\cdot a_3+1$
...

Erkläre, warum das so ist. Benutze das rekursive Löseverfahren, das im letzten Abschnitt entwickelt wurde.

(b) Beschreibe die Gesetzmäßigkeit jetzt allgemein. Ergänze hierzu die Formel für $a_n$.

$a_1=1$
$a_2=2\cdot a_1+1$
$a_3=2\cdot a_2+1$
$a_4=2\cdot a_3+1$
...
$a_n=...$ (für $n=2,3,...$)