Turm von Ionah
Der „Turm von Ionah“ ist die Umkehrung (in vertikaler Richtung) der berühmten Aufgabe, den „Turm von Hanoi“ entstehen zu lassen. Aus dieser Umkehrung entstand auch der Name „Ionah“, indem die Reihenfolge der Buchstaben H, A, N, O, I durch Lesen von rechts nach links in I, O, N, A, H übergeht.
Die Geschichte des Turmes von Ionah ist also auch die Geschichte des Turmes von Hanoi (mitunter auch als „Turm des Brahma“ oder das „Weltende-Puzzle“ bezeichnet; siehe weiter unten).
Der Turm von Hanoi — und damit auch der Turm von Ionah — wurde im Jahre 1883 von dem französischen Mathematiker Francois Éduord Lucas (1842–1891) erfunden. Er war zunächst einfach ein Spiel mit dem Namen „M. Claus“.
In einer einfachen Form besteht der Turm von Ionah — wie im ERLEBNISLAND MATHEMATIK — aus fünf Kreisscheiben, die übereinander konzentrisch in einer Vertiefung liegen. Zum Turm von Ionah gehören zwei gleichartige Vertiefungen (vgl. Abbildung 1). Die Aufgabe des Spieles besteht darin, die Scheiben des Turmes von einer der drei Vertiefungen in eine zweite zu überführen, wobei folgende zwei Regeln zu beachten sind:
- Man darf stets nur eine Scheibe umlegen.
- Man darf eine kleinere nicht auf eine größere Scheibe legen.
Die dritte Vertiefung dient als zusätzliches Zwischenlager.
Die Idee zu diesem Spiel als Turm von Hanoi bezog F. E. Lucas aus folgender asiatischer Legende:
Im großen Tempel der indischen Stadt Benares (heute: Varanasi), unter dem Dom, der die Mitte der Welt symbolisiert, ruht eine Messingplatte, in der Diamantnadeln befestigt sind, jede eine Elle (ca. 50–80cm) hoch und stark wie der Körper einer Biene. Bei der Erschaffung der Welt hat Gott 64 Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Messingplatte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen. Das ist der Turm von Brahma. Tag und Nacht sind die Priester unablässig damit beschäftigt, den festgeschriebenen und unveränderlichen Gesetzen von Brahma folgend, die Scheiben von einer Diamantnadel auf eine andere zu setzen, wobei der oberste Priester nur jeweils eine Scheibe auf einmal umsetzen darf, und zwar so, dass sich nie eine kleinere Scheibe unter einer größeren befindet. Sobald alle vierundsechzig Scheiben von der goldenen Nadel, auf die Gott sie bei seiner Erschaffung der Welt gesetzt hat, auf eine der anderen Nadeln gebracht sein werden, werden — so die Legende — der Turm samt dem Tempel und allen Brahmanen zu Staub zerfallen, und die Welt wird mit einem Donnerschlag untergehen.
Und … die Zahl der Scheibenbewegungen durch den obersten Priester wäre — folgt man der Legende — „im günstigsten Fall“:
Würde eine Scheibenbewegung nur eine Sekunde erfordern, dauerte das Umsetzen der 64 goldenen Scheiben den unvorstellbaren Zeitraum von 580 Milliarden Jahren. (Der Urknall, also die Entstehung des Universums, fand nach heutigen Erkenntnissen vor ca. 13,8 Milliarden Jahren statt!)
Im ERLEBNISLAND MATHEMATIK ist die Anzahl der Scheiben des Turmes von Ionah nicht 64, sondern 5. Wie die unten folgende mathematische Überlegung zeigt, ist die minimale Anzahl der Bewegungen der fünf Scheiben , um den Turm von Ionah in seine bisherige Gestalt umzusetzen (unter Berücksichtigung der obigen Regeln).
Und nun … die Mathematik dazu:
Es sei die Anzahl der Scheiben. Weiter bezeichne
den ursprünglichen Turm mit den Scheiben
(von „oben“ nach „unten“;
),
den „Zwischenlagerturm“, und
den „Zielturm“.
Die Anzahl der Züge der optimalen Lösung (d.h. die minimale Anzahl von Zügen) ist dann . Dies lässt sich mittels Induktion wie folgt beweisen:
Für eine einzelne Scheibe (also ) ist diese Aussage sicher richtig, denn diese muss nur von
nach
verschoben werden; die optimale Zugfolge besteht dann also — wie behauptet — aus einem einzigen Zug (
).
Nehmen wir also an, wir haben Scheiben gegeben. Um die kleinste (am Anfang zuunterst liegende) Scheibe
von
nach
zu bewegen, müssen wir zunächst die darüberliegenden Scheiben
nach
umlegen. Dies kostet uns nach der Induktionsannahme für
(mindestens)
Züge (die Rollen von
und
sind hier vertauscht). Nachdem wir diese vollzogen haben, können wir die Scheibe
nach
umlegen und anschließend, mit derselben Prozedur wie zuvor, die Scheiben
in (mindestens)
Zügen von
nach
umlegen (hierbei sind nun gegenüber dem ursprünglichen Problem die Rollen von
und
vertauscht). Summieren wir alle Züge auf, so erhalten wir also wie behauptet:
Auf dieselbe Weise lässt sich nun auch bestimmen, wie oft und bei welchen Zügen jede Scheibe bei der eben beschriebenen optimalen Zugfolge bewegt wird:
Wir behaupten, dass die Scheibe genau in den Zügen
also insgesamt -mal bewegt wird (zum Test:
ergibt die Gesamtanzahl aller Züge). Wieder beweisen wir dies mit Induktion:
Für ist die Aussage richtig, denn die Scheibe
wird dann nur im Zug
bewegt.
Nehmen wir also an. Dann führen wir in den ersten
Zügen das Spiel mit den
Scheiben
durch, wobei die Rollen von
und
vertauscht sind. Die Scheibe
(
) wird also in diesem Teil des Spiels nach Induktionsannahme genau in den Zügen
bewegt. Dies entspricht genau der ersten Hälfte der Züge von wie sie oben aufgeführt sind. Dann wird die Scheibe
im Zug Nummer
von
nach
bewegt — wie behauptet. Anschließend führen wir wieder unser Spiel mit den
Scheiben
durch, wobei nun die Rollen von
und
vertauscht sind. Es ergibt sich, dass die Scheibe
(
) weiterhin in den Zügen
bewegt wird, woraus die Behauptung folgt.
Mit diesen Überlegungen ist es nun möglich, an jedem Punkt der Zugfolge zu bestimmen, welche Scheibe als nächste bewegt werden muss. Das sich ergebende Muster entspricht überraschenderweise genau dem Zählen im Binärsystem: Wenn Du herausfinden willst, welche Scheibe Du im -ten Zug gemäß dem eben beschriebenen opimalen Vorgehen bewegen musst, schreibe die Zahl
im Binärsystem und sieh bis zu welcher Stelle die Nullen und Einsen beim Übergang von
zu
„geflippt“ werden müssen. Ist zum Beispiel
, dann ist
im Binärsystem, sodass Du, um eins weiterzuzählen, alle ersten vier Stellen flippen musst:
. Also musst Du im achten Zug die vierte Scheibe (so es vier Scheiben gibt; wenn nicht bist Du schon fertig) bewegen. Zu diesem interessanten Zusammenhang siehe auch die Videos [4] und [5] vom YouTuber 3Blue1Brown.
Als Algorithmus
Die obige Vorgehensweise kann durch folgenden Algorithmus zusammengefasst werden:
Es sei
… Lösung eines Spieles, das fordert,
Ringe aus der (kreisförmig abgestuften) Form
(vgl. Abbildung 1) in die entsprechende Form
zu bewegen;
… die Form, die von den Formen
und
verschieden ist (die „dritte“ Form);
… man bewege einen Ring (direkt) von
nach
(bereits definiert, aber hier zum besseren Verständnis nochmal erwähnt).
Dann erhält man für die obige Aufgabe folgenden rekursiven Algorithmus (in Pseudocode):
Literatur
[1] Gardner, M.: Mathematical Puzzles & Diversions, New York, 1959.
[2] van Delft, P., und Botermans, J.: Denkspiele der Welt, München, 1998.
[3] Link zum Applet