Arbeitsblatt: Die Türme von Hanoi

Geometrische Folgen Die Türme von Hanoi 1 Die Türme von Hanoi Bei diesem Spiel sind auf einem Brett drei stehende Stäbe befestigt, auf die Scheiben unterschiedlichen Durchmessers (mit Loch in der Mitte) gesteckt werden können und von denen man diese auch abheben kann. (Die drei Stäbe sind mit Platz 1 3 benannt.) Aufgabenstellung (Fig. 1) geg: Turm, der aus übereinander gelegten Scheiben abnehmenden Durchmessers besteht und sich auf Platz 1 befindet. ges: minimalste Anzahl Schritte Sn in welchen sich der gegebene Turm von Platz 1 abund auf Platz 3 wieder aufbauen lässt, wobei auch Platz 2 zum Zwischenlagern von Scheiben benützt werden darf. Als 1 Schritt gilt das Abheben der obersten Scheibe von einem der drei Plätze mit dem Ablegen dieser auf einem der beiden anderen. Dabei darf die Scheibe nicht auf eine solche kleineren Durchmessers zu liegen kommen. Platz 1 Platz 2 Platz 3 Fig. 1: Turm (n 8) in Anfangsposition (Platz 1) und Endposition (Platz 3) Beispiel für n3 (Fig. 2.1 2.8): Fig. 2.1: Anfangsposition Fig. 2.2: nach dem 1. Schritt Fig. 2.3: nach dem 2. Schritt Fig. 2.4: nach dem 3. Schritt Geometrische Folgen Die Türme von Hanoi Fig. 2.5: nach dem 4. Schritt Fig. 2.6: nach dem 5. Schritt Fig. 2.7: nach dem 6. Schritt Fig. 2.8: nach dem 7. Schritt Endposition) Es ist also offenbar S3 7. Vorgehen: überlege dir, in welche Stellung die unterste Scheibe verschoben werden kann bestimme eine Rekursionsformel für Sn entwickle mit ihr S2 S3 S4 in Summen und Produkte von Zahlen finde die Gesetzmässigkeit in diesen Entwicklungen bestimme mit der Formel für diese Gesetzmässigkeit Sn 2