Die Legende des Turms von Benares
(auch bekannt als Turm von Hanoi)

Edouard Anatole Lucas, ein französicher Mathematiker, erzählte 1883 folgende Legende:

In einem Tempel in der indischen Stadt Benares liegen 64 kostbare Scheiben aus Diamant zu einem Turm aufgeschichtet. Jede Scheibe ist ein wenig kleiner als die Scheibe auf der sie ruht.
Eine Priesterorden hat nun die Aufgabe erhalten den Turm unter Beachtung heiliger Regeln zu einer anderen Stelle im Tempel zu bewegen. Die Scheiben sind so kostbar, daß sie nur auf einem von drei Plätzen im Tempel liegen dürfen, dem Platz wo der Turm zu Beginn stand, dem wo er aufgebaut werden soll und einem Platz dazwischen. Die Scheiben sind schwer und zerbrechlich, daher darf immer nur eine der Scheiben bewegt werden, niemals mehrere zur gleichen Zeit Die letzte Regel besagt, daß zu keiner Zeit eine 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.

Wer der Legende Glauben schenkt, wird sich spätestens bei der Planung der nächsten Party oder dem Kauf von Aktien-Optionen die Frage stellen: "Wie lange werden die Mönche wohl noch brauchen, bis der Turm umgebaut ist ?"

Ich fasse die Aufgabe nochmal zusammen:
64 Scheiben, alle unterschiedlich groß, liegen zu einem Turm aufgeschichtet auf dem ersten von drei markierten Feldern. Der Turm soll nun auf das dritte markierte umgebaut werden. Dabei müssen folgende Regeln beachtet werden:
1. Die Scheiben dürfen nicht außerhalb der markierten Felder abgelegt werden.
2. Pro Zug darf nur eine Scheibe bewegt werden.
3. Eine Scheibe darf niemals auf eine kleinere Scheibe gelegt werden.

Auch wer der Geschichte nicht glaubt, obgleich sie nicht der BILD-Zeitung entnommen wurde, wird sich vielleicht die grundlegende Frage stellen: "Kann der Turm überhaupt unter Beachtung der Regeln umgebaut werden?". Dies ist die Frage nach der Existenz einer Lösung, und die kann auf frappierend einfache Weise gelöst mit. Befassen wir uns zunächst mit einer Lösungsstrategie. Für ganz Eilige gibt es die Dauer auch sofort.