Wissenschaftssommer 2008

Der Turm von Hanoi

Die Aufgabe

Auf einem von drei Stäben sitzen 7 Scheiben, die kleinste oben, die größte unten.
Die Aufgabe besteht darin, diese Scheiben auf einen der anderen Stäbe zu bringen, wobei folgende Regeln zu beachten sind:
In jedem Schritt darf nur eine Scheibe bewegt werden und nie darf eine größere Scheibe auf einer kleineren liegen.

  • Was ist die kleinste Anzahl von dazu notwendigen Schritten?
  • Wann und wie bewegst du bei dieser Lösung die kleinste Scheibe?
  • Findest du auch Regeln für die Bewegung jeder anderen Scheibe?

Die Legende

Der Mathematiker Edouard Lucas erfand diese Geschichte [1]:

Im Großen Tempel von Benares, unter dem Dom, der die Mitte der Welt markiert, ruht eine Platte, in der 3 Diamantnadeln befestigt sind, jede eine Elle hoch. Bei der Erschaffung der Welt hat Gott 64 Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Platte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen. Das ist der Turm von Brahma.
Ein Priesterorden hat nun die Aufgabe erhalten, den Turm unter Beachtung heiliger Regeln von der einen Diamantnadel zur anderen zu bewegen. Die Scheiben sind so kostbar, dass sie nur auf einer der drei Diamantnadeln liegen dürfen. Die Scheiben sind schwer und zerbrechlich, daher darf immer nur eine der Scheiben bewegt werden, niemals mehrere zur gleichen Zeit. Die letzte Regel besagt, dass zu keiner Zeit eine große Scheibe auf einer kleineren Scheibe liegen darf.

Wenn der Turm an einer Stelle abgebaut und an andere Stelle wieder ganz aufgebaut wurde, wird der Tempel und mit ihm die ganze Welt zu Staub zerfallen. Wie viele Züge sind mindestens nötig, um den Turm vollständig umzusetzen?

Hintergrund

Diese Aufgabe ist ein Klassiker. Das Lösungsverfahren ist rekursiv, seine Korrektheit und Optimalität werden durch vollständige Induktion gezeigt. Deswegen gehört die Aufgabe zum Pflichtprogramm für Informatik-Erstsemester. Das berühmte Lehrbuch [2] wird durch die Türme von Hanoi eröffnet.

Varianten

Man kann die möglichen Bewegungen der Scheiben einschränken:

  • nur zwischen benachbarten Türmen (aber nicht zwischen dem ersten Turm und dem letzten Turm)
  • nur im Uhrzeigersinn (vom ersten zum zweiten, zweiten zum dritten usw. und vom letzten zum ersten)
Dadurch wird die Lösung erschwert: man benötigt mehr Züge. Welche der Einschränkungen ist härter? Siehe [2, Übungsaufgaben zum ersten Kapitel].

Man kann weitere Türme hinzufügen, dadurch werden kürzere Lösungen möglich. Diese folgen komplizierteren Mustern. Für keines konnte man bisher beweisen, daß es optimal ist. Die Aufgabe wird noch unübersichtlicher, wenn man Türme hinzufügt und gleichzeitig Züge einschränkt.

  • Ist man bei 4 Türmen im Uhrzeigersinn schneller als bei 3 Türmen ohne Einschränkungen?
Probiere mit den Holzscheiben oder beim Online-Spiel!

Komplexitätsklasse: PSPACE
Selber Ausprobieren:Hier!
Quellen / Fußnoten:[1] Edouard Lucas: Recreations mathematiques, Gauthier-Villars, Paris 1891-1894. (Türme von Hanoi in Band 3, Seiten 55-59)
[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics, Addison-Wesley 1989.

© LSGM