| Autor |
Beitrag |
    
Kerstin Striepen (Crazykess)
| | Veröffentlicht am Sonntag, den 11. November, 2001 - 15:53: | 
|
Hallo!
Ich habe eine Frage zum Turm von Benares!
Die Formel die ich herausgefunden habe lautet
M(n)= 2^n - 1
Ich soll diese mittels vollständiger Induktion für alle n e N beweisen.
Ich stehe am Semesteranfang und begreife die vollst. Induktion gar nicht! Ich hoffe auf eure Hilfe!
Vielen Dank schon mal
Ciao
Kerstin |
H.R.Moser,megamath.
| | Veröffentlicht am Sonntag, den 11. November, 2001 - 21:42: |
|
Hi Kerstin,
Offenbar handelt es sich bei Deiner Aufgabe
um das bekannte Problem der Türme von Hanoi,
das im Jahre1883 von Edouard Lucas gestellt wurde
und seither auch in der Form eines Spiels bekannt ist.
Auf drei Säulen A,B,C sind Scheiben zu plazieren.
Zu Beginn des Spiels liegen n Scheiben, die von oben
nach unten strikte monoton wachsende Durchmesser haben,
auf der Säule A.
Diese Scheiben sind nun alle von A nach B zu bringen,
wobei die Säule C zu Hilfe genommen wird
Dabei darf nie mehr als eine Scheibe gleichzeitig bewegt werden,
und es darf auch nicht eine grössere Scheibe auf eine kleinern
gelegt werden.
Gesucht wird die Minimalzahl T(n) der Scheibentransporte.
Es ist T(3) = 7 wie der folgende Ablauf des Verfahrens für n = 3
zeigt:
Scheibe 1 von Turm A nach Turm B
Scheibe 2 von Turm A nach Tum C
Scheibe 1 von Turm B nach Turm C
Scheibe 3 von Turm A nach Turm B
Scheibe 1 von Turm C nach Turm A
Scheibe 2 von Turm C nach Turm B
Scheibe 1 von Turm A nach Turm B
Für T = T(n) gilt die Rekursionformel:
T(n) = 2* T(n-1) + 1 , n= 2,3,......................................................(1)
T(1) = 1.........................................................................................(2)
Daraus kann die geschlossene Form
T(n) = 2^n -1 .................................................................................(3)
hergeleitet werden
Es geht bei Deiner Aufgabe darum, die Formel (3)
induktiv zu beweisen.
Verankerung (Induktionsanfang): T(1) = 2^1 - 1 = 1; in Ordnung !
Schluss von (n-1) auf n:
Induktionsvoraussetzung:T(n-1) =2^(n-1)-1
Induktionsschluss:
T(n) = 2*T(n-1) +1 = 2* [2^(n-1) - 1] +1= 2 ^ n -2+1 = 2^n-1 ,
wie es sein muss !
Mit freundlichen Grüßen
H.R.Moser,megamath. |
Kerstin Striepen (Crazykess)
| | Veröffentlicht am Montag, den 12. November, 2001 - 20:37: |
|
Hallo du Mathegenie!
Ich danke dir ganz herzlich! So langsam blicke ich dahinter, was es mit der Induktion auf sich hat. Viele Liebe Grüße
Kerstin |
|
