Ein Umschichtproblem
Einen Turm umschichten
Einer Geschichte zufolge soll im Tempel zu Benares - das ist eine heilige Stadt
in Indien -
ein Turm aus 64 goldenen, der Größe nach geordneten Scheiben stehen.
Die Mönche des Tempels erhalten die Aufgabe,
die Scheiben an einen anderen Ort zu bringen. Dabei müssen sie einige Regeln beachten:
Es darf immer nur eine Scheibe transportiert werden.
Scheiben können auf einem (einzigen) Hilfsstapel zwischenzeitlich abgelegt werden.
Auch auf dem (teilweise abgebauten) Ausgangsturm können Scheiben zwischenzeitlich abgelegt werden.
Es darf aber nie eine größere Scheibe auf eine kleinere gelegt werden.
Wenn der neue Turm fertig ist, dann ist das Ende der Zeit erreicht.
Das Spiel zur Geschichte gibt es in verschiedenen Versionen. Auf dem Foto besteht der Ausgangsturm aus 5 Holzscheiben.
Wir werden uns hier mit folgenden Fragen beschäftigen.
Mit welcher Strategie kann man einen Turm mit einer vorgegeben Anzahl von Scheiben umschichten? Wie viele Scheibenbewegungen sind hierzu erforderlich? Wie lange dauert es wohl, einen 64-Scheiben-Tum umzuschichten?
Im folgenden Abschnitt findest du ein Applet, mit dem du auf die Suche nach Antworten gehen kannst.
