Aufgabe
Behauptung: Die Türme von Hanoi-Aufgabe mit n Scheiben
erfordert 2n − 1 Züge zu deren Lösung.
1. Beweisen Sie die Behauptung per vollständiger Induktion.
2. Warum ist das Argument, dass ein fiktives Java-Programm nach
2n − 1 Zügen fertig ist, kein Beweis der Behauptung?
Lösung
1. Induktionsanfang.
Zu zeigen, die Behauptung gilt für n = 1.
Eine Scheibe (n = 1) erfordert einen Zug (21 − 1 = 1) .
Induktionsannahme
Es gibt ein n, sodass die Behauptung f¨ur alle Zahlen kleiner gleich n gilt.
Induktionsschritt
Zu zeigen, mit der Induktionsannahme, gilt die Behauptung auch für n + 1.
Die Darstellung mit Originalplatz (O), Hilfsplatz (H) und Zielplatz (Z),
ist wie folgt.
Türme von Hanoi Induktion Aufgabe+Lösung
Die Aufgabe, einen korrekten Turm (Scheiben werden von oben nach unten kleiner)
für die obersten n Scheiben vom Orignialplatz O, mit interims Hilfsplatz Z auf den
interims Zielplatz H zu uberführen in 2n −1 Schritten lösbar, laut Induktionsannahme.
Ein Schritt braucht man um die Scheibe n+1, die noch auf O liegt nach Z zu legen.
Mit Induktionsannahme braucht man nocheinmal 2n − 1 Schritte um den Turm aus
n Scheiben vom interims Originalpaltz H mit interims Hilfsplatz O auf den Zielplatz
Z (wo die Scheibe n + 1 schon liegt) zu uberführen
Macht 2n − 1 + 1 + 2n − 1 = 2 · (2n − 1) + 1 = 2n+1 − 2 + 1 = 2n+1 − 1 Schritte.
Thats it! 