Türme von Hanoi < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:14 So 28.10.2007 | | Autor: | Sunsh1ne |
| Aufgabe | Ein bekanntes mathematisches Spiel ist der 'Turm von Hanoi'. Auf einem von frei Stäben sitzen n der Größe nach geordnete Scheiben, die kleinste oben. Die Aufgabe besteht darin, diese Scheiben auf einen der anderen Stäbe zu bringen, wobei folgende Regeln zu beachten sind:
1. In jedem Schritt darf nur eine Scheibe bewegt werden.
2. Nie darf eine größere Scheibe auf einer kleineren liegen.
Zeigen Sie mit vollständiger Induktion, dass man die aufgabe mit [mm] 2^n [/mm] -1
Schritten lösen kann. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Guten Morgen :)
Ich soll die Aufgabe bis morgen lösen, hab aber leider gar keinen Ansatz für die Lösung. Versteht einer von euch vielleicht, wie man hier vorgehen muss?
Bin für jeden Tip dankbar!
Viele Grüße, Sunny
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:55 So 28.10.2007 | | Autor: | Loddar |
Hallo Sunny!
Das eigentliche Prinzip der vollständigen Induktion ist aber klar, oder?
Bei dieser Aufgabe muss man sich klar machen, wie man eine Turm mit insgesamt $n_$ Scheiben vom Punkt $A_$ nach Punkt $B_$ schafft.
Dafür transportiere ich die obersten $n-1_$ Scheiben nach $C_$ , lege die unterste (= größte) Scheibe von [mm] $A\rightarrow [/mm] B$ . Und nun wiederum den $n-1_$-Scheiben-Turm von [mm] $C\rightarrow [/mm] B$ .
Damit habe ich also für einen Turm mit $n_$ Scheiben insgesamt $A(n-1)_$ (=Anzahl der Bewegungen zur Verschiebung eines Turmes mit $n-1_$ Scheiben) + 1 Bewegung für die größte Scheibe sowie wiederum $A(n-1)_$ Bewegungen vollzogen.
In rekursiver Drstellung bedeutet dies also:
$$A(n+1) \ = \ 2*A(n)+1$$
Es ist also nun mittels vollständiger Induktion zu zeigen, dass ich diese rekursive Vorschrift auch explizit als $A(n) \ = \ [mm] 2^n-1$ [/mm] darstellen kann.
Gruß
Loddar
|
|
|
|
