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“:

$2^{64}-1=18.446.744.073.709.551.615.$

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 $2^5-1=31$ , um den Turm von Ionah in seine bisherige Gestalt umzusetzen (unter Berücksichtigung der obigen Regeln).

Und nun … die Mathematik dazu:

Es sei $n$ die Anzahl der Scheiben. Weiter bezeichne $A$ den ursprünglichen Turm mit den Scheiben $S_1, S_2,\ldots , S_n$ (von „oben“ nach „unten“; $n\geq 1$ ), $B$ den „Zwischenlagerturm“, und $C$ den „Zielturm“.

Die Anzahl der Züge der optimalen Lösung (d.h. die minimale Anzahl von Zügen) ist dann $z_n=2^n-1$ . Dies lässt sich mittels Induktion wie folgt beweisen:

Für eine einzelne Scheibe (also $n=1$ ) ist diese Aussage sicher richtig, denn diese muss nur von $A$ nach $C$ verschoben werden; die optimale Zugfolge besteht dann also — wie behauptet — aus einem einzigen Zug ( $z_1=2^1-1=1$ ).

Nehmen wir also an, wir haben $n\geq 2$ Scheiben gegeben. Um die kleinste (am Anfang zuunterst liegende) Scheibe $S_n$ von $A$ nach $C$ zu bewegen, müssen wir zunächst die darüberliegenden Scheiben $S_1,\ldots,S_{n-1}$ nach $B$ umlegen. Dies kostet uns nach der Induktionsannahme für $n-1$ (mindestens) $2^{n-1}-1$ Züge (die Rollen von $B$ und $C$ sind hier vertauscht). Nachdem wir diese vollzogen haben, können wir die Scheibe $S_n$ nach $C$ umlegen und anschließend, mit derselben Prozedur wie zuvor, die Scheiben $S_1,\ldots,S_{n-1}$ in (mindestens) $2^{n-1}-1$ Zügen von $B$ nach $C$ umlegen (hierbei sind nun gegenüber dem ursprünglichen Problem die Rollen von $A$ und $B$ vertauscht). Summieren wir alle Züge auf, so erhalten wir also wie behauptet:

$z_n=z_{n-1}+1+z_{n-1}=2z_{n-1}+1=2(2^{n-1}-1)+1=2^n-1.$

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 $S_k$ genau in den Zügen

$1\cdot 2^k-2^{k-1},2\cdot 2^k-2^{k-1},\ldots,2^{n-k}\cdot 2^k-2^{k-1},$

also insgesamt $N_k=2^{n-k}$ -mal bewegt wird (zum Test: $N_1+\cdots+N_n=2^{n-1}+2^{n-2}+\cdot+2+1=2^n-1=z_n$ ergibt die Gesamtanzahl aller Züge). Wieder beweisen wir dies mit Induktion:

Für $n=1$ ist die Aussage richtig, denn die Scheibe $S_1$ wird dann nur im Zug $1=2^1-2^{1-1}$ bewegt.

Nehmen wir also $n\geq 2$ an. Dann führen wir in den ersten $z_{n-1}=2^{n-1}-1$ Zügen das Spiel mit den $n-1$ Scheiben $S_1,\ldots,S_{n-1}$ durch, wobei die Rollen von $B$ und $C$ vertauscht sind. Die Scheibe $S_k$ ( $1\leq k\leq n-1$ ) wird also in diesem Teil des Spiels nach Induktionsannahme genau in den Zügen

$1\cdot 2^k-2^{k-1},2\cdot 2^k-2^{k-1},\ldots,2^{n-1-k}\cdot 2^k-2^{k-1}$

bewegt. Dies entspricht genau der ersten Hälfte der Züge von $S_k$ wie sie oben aufgeführt sind. Dann wird die Scheibe $S_n$ im Zug Nummer $z_{n-1}+1=2^{n-1}=1\cdot 2^n-2^{n-1}$ von $A$ nach $C$ bewegt — wie behauptet. Anschließend führen wir wieder unser Spiel mit den $n-1$ Scheiben $S_1,\ldots,S_{n-1}$ durch, wobei nun die Rollen von $A$ und $B$ vertauscht sind. Es ergibt sich, dass die Scheibe $S_k$ ( $1\leq k\leq n-1$ ) weiterhin in den Zügen

$2^{n-1}+1\cdot 2^k-2^{k-1}=(2^{n-1-k}+1)\cdot 2^k-2^{k-1},\ldots,2^{n-1}+2^{n-1-k}\cdot 2^k-2^{k-1}=2^{n-k}\cdot 2^k-2^{k-1}$

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 $m$ -ten Zug gemäß dem eben beschriebenen optimalen Vorgehen bewegen musst, schreibe die Zahl $m-1$ im Binärsystem und sieh bis zu welcher Stelle die Nullen und Einsen beim Übergang von $m-1$ zu $m$ „geflippt“ werden müssen. Ist zum Beispiel $m=8$ , dann ist $m-1=111$ im Binärsystem, sodass Du, um eins weiterzuzählen, alle ersten vier Stellen flippen musst: $m=1000$ . 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

$\mathrm{Sol}[n,x,y]$ … Lösung eines Spieles, das fordert, $n$ Ringe aus der (kreisförmig abgestuften) Form $x$ (vgl. Abbildung 1) in die entsprechende Form $y$ zu bewegen;
$\mathrm{not}(x, y)$ … die Form, die von den Formen $x$ und $y$ verschieden ist (die „dritte“ Form);
$\mathrm{Sol}[1, x, y]$ … man bewege einen Ring (direkt) von $x$ nach $y$ (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):

$\mathrm{Sol}[n,x,y]\coloneqq\{\mathrm{Sol}[n-1,x,\mathrm{not}(x,y)];\mathrm{Sol}[1,x,y];\mathrm{Sol}[n-1,\mathrm{not}(x,y),y]\}.$

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

[4] https://www.youtube.com/watch?v=2SUvWfNJSsM

[5] https://www.youtube.com/watch?v=bdMfjfT0lKk