|
| 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), ...
Wir suchen nach einer bequemen expliziten Darstellung
explizite 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)
|
|
|
|
|
|
|
|
... |
explizite Darstellung
Dann erhält man als explizite Darstellung:
M(n)=2n-1
Den Beweis führt man per vollständiger Induktion.
Nun lässt sich M(20)=1.048.575 leicht errechnen.
|
|
|
|
