MathePrisma, Rekursive Folgen


		Rekursive Folgen (Türme von Hanoi²)

Situation

Wir betrachten das Spiel mit fünf Scheiben.

Beobachte

Die Lösung

	Betrachte den 5er-Turm als 4er-Turm auf einer Scheibe, die größer ist als alle 4 Scheiben des Turms. Bewege zuerst den oberen Turm.
	Diesen Turm kann man in 15 Schritten (siehe Demo-Film) an einer anderen Stelle wieder aufbauen.
	Die Scheibe wechselt den Platz mit nur einem Zug.
	Und mit 15 weiteren Umlegungen wandert der Turm auf die Scheibe zurück.

M(n)=minimale Anzahl an Umlegungen bei n Scheiben

Wir können diese Anzahl der Umlegungen damit rekursiv darstellen als
M(5)=M(4)+1+M(4)

Dies geht mit allen anderen Türmen genauso.

rekursive Darstellung

Startwert	M(1)= 1 ist klar!
Vorschrift	M(n)=2·M(n-1)+1 für n>1

Ist das Turmproblem damit gelöst? Eigentlich schon.

Doch auch hier fordert die Frage nach der Lösung bei 20 Scheiben einen unangenehmen Arbeitsaufwand, denn man braucht dazu M(19), dann M(18), M(17), ...

explizite Darstellung

Wir suchen nach einer bequemen expliziten Darstellung

Betrachtet man die Zahlenfolge der Lösungen:

n 1 2 3 4 5 6 7 ...

M(n) 1 3 7 15 31 63 127 ...

M(n) 2-1 4-1 8-1 16-1 32-1 64-1 128-1 ...

M(n) 2¹-1 2²-1 2³-1 2⁴-1 2⁵-1 2⁶-1 2⁷-1 ...

explizite Darstellung

Dann erhält man als explizite Darstellung:

M(n)=2ⁿ-1

Den Beweis führt man per vollständiger Induktion.

Nun lässt sich M(20)=1.048.575 leicht errechnen.

Seite 7/9