Mathematische Knobelei: Der Turmzauberer von Hanoi
Die Welt ist kleiner geworden. In Neuseeland trifft man auf seinen Bäcker, in Tunesien läuft einem der Dackelfreund von nebenan über den Weg, und die Malediven teilt man sich mit dem Kollegen aus der Buchhaltung. Da muss es schon ein ausgefallenes Reiseziel wie Vietnam sein. Und ein Souvenir mit dem gewissen Etwas natürlich.
Schauen Sie hier, ehrenwerte Mister. Werfen Sie Blick auf mein unwürdiges Angebot von erlesene Ware. Feinste Handarbeit, ehrenwerte Mister. Aus echte Elfenbein und Tigerzahn. Traditionelle vietnamesische Schnitzkunst. Von uralte Meister hergestellt. Sein Vermögen wert. Aber ich verkaufen billig.
Sehen Sie, ehrenwerte Mister. Türme von Hanoi in jede Größe. Mit Spielfeld aus feinste Edelholz. Fühlen Sie, ehrenwerte Mister, wie glatt Holz sein. Fühlen auch Felder von Figuren. Echte Jadestein, alle drei Felder. Machen Spiel schon zu Vergnügen für Auge. Ich anbieten Spiel mit Türme in jede Höhe. Mit drei, vier, fünf oder mehr Steine. Jede Höhe. Immer lösbar. Spiel gut für Gesundheit von Kopf. Trainieren Denken von Raum.
Regeln einfach, können jedes Kind. Zuerst bauen Turm auf eine Feld. Stellen Steine übereinander, immer kleine Stein auf große, nie große auf kleine. Dann Aufgabe, Turm umsetzen auf zweite Feld. Stein für Stein. Darf benutzen dritte Felder für Zwischenlager. Spiel fertig, wenn Turm ganz auf neue Feld.
Sehen Sie, ehrenwerte Mister. Türme von Hanoi in jede Größe. Mit Spielfeld aus feinste Edelholz. Fühlen Sie, ehrenwerte Mister, wie glatt Holz sein. Fühlen auch Felder von Figuren. Echte Jadestein, alle drei Felder. Machen Spiel schon zu Vergnügen für Auge. Ich anbieten Spiel mit Türme in jede Höhe. Mit drei, vier, fünf oder mehr Steine. Jede Höhe. Immer lösbar. Spiel gut für Gesundheit von Kopf. Trainieren Denken von Raum.
Regeln einfach, können jedes Kind. Zuerst bauen Turm auf eine Feld. Stellen Steine übereinander, immer kleine Stein auf große, nie große auf kleine. Dann Aufgabe, Turm umsetzen auf zweite Feld. Stein für Stein. Darf benutzen dritte Felder für Zwischenlager. Spiel fertig, wenn Turm ganz auf neue Feld.
Oh, ich ahnen, ehrenwerte Mister kennt Spiel bereits. Verzeihen mir unwürdige Wurm lange Erklärung. Ehrenwerte Mister sicher schon wissen, auf welche Feld erste, kleinste Stein verschieben muss, wenn Turm von Feld A nach B sollen. Und ehrenwerte Mister natürlich auch sagen können, wie viele Züge mindestens brauchen, um Turm mit n Steine umzusetzen. Ehrenwerte Mister wie geschaffen für diese Souvenir. Wenn Lösungen sagen, ich machen guten Preis.
Aufgepasst liebe Asienreisenden! Es darf mit Fug und Recht bezweifelt werden, dass jenes feilgebotene Knobelspiel tatsächlich von einem uralten Meister stammt, wird doch das berühmte Scheibchenschieben eher einem französischen Mathematiker des 19. Jahrhunderts zugeschrieben. Doch das tut unserer aktuellen mathematischen Knobelei keinerlei Abbruch.
Hand aufs Herz - haben Sie die Lösung zu den Türmen von Hanoi selbst erknobelt oder sich einer der vielen Seiten im Internet bedient? Wie auch immer, das Problem ist eigentlich überschaubar - vorausgesetzt man beginnt zuerst mit einer kleinen Anzahl von Steinen. Dabei liefert der triviale Fall von genau einer Turm-Scheibe auch genau einen Zug: nämlich von A nach B. Bei zwei Steinen müssen wir mit der kleinen Scheibe zunächst nach C ausweichen, um dann die große auf B zu setzen und schließlich die kleine von C nach B zu heben. Drei Züge sind also nötig.
Um die Schreibarbeit in Grenzen zu halten, verwenden wir nun folgende Notation: Die Scheiben sein von der kleinsten zur größten von 1 bis n durchnummeriert. Die Ablageplätze tragen, wie bereits erwähnt, die Bezeichnungen A, B und C. Das Versetzen eines bestimmten Turmsegments auf einen Stapel drücken wir nun einfach durch die Nummer der jeweiligen Scheibe mit nachgestelltem Buchstaben des Zielstapels aus. Bei 1C wird also das kleinste Segment auf den Stapel C geschoben.
In dieser Schreibeweise lautet die Lösung für drei Steine von A nach B folgendermaßen: 1B, 2C, 1C, 3B, 1A, 2B, 1B. 7 Züge sind also für eine Turmversetzung nötig, wobei der erste Zug bereits zum späteren Standort des Turms führt.
Analog lässt sich das Spielchen für 4 und mehr Turmsegmente fortführen. Wobei sich die Schieberei großer Türme stets auf die kleiner Türme zurückführen lässt. Um beispielsweise einen 4er Turm zu versetzen, müssen wir zuerst seine Spitze - im Prinzip ein 3er Turm - an einen geeigneten Ausweichplatz - in unserem Fall C - manövrieren. Anschließend bewegen wir die größte Scheibe, das Fundament, an den gewünschten Ort, in unserem Fall B, und versetzen anschließend den 3er Turm auf dieses Fundament. Um einen 4er-Turm zu bewegen, müssen wir haben also zweimal einen 3er Turm verschieben und einen zusätzlichen Schritt für das Versetzen des Fundaments machen. Das gilt in gleicher Weise auch für alle größeren Türme, sodass man auf folgenden rekursiven Ausdruck für die Anzahl der Züge bei n Turmsegmenten kommt:
Z(n+1) = 2·Z(n)+1
Das Ganze lässt sich etwas handlicher auch durch eine Rekursionsformel ausdrücken:
Z(n) = 2n-1
Der Beweis kann beispielsweise durch vollständige Induktion erfolgen.
Wird mit einer ungeraden Anzahl von Turmsegmenten gespielt, dann darf der erste Zug bereits an den künftigen Standort führen. Ist die Zahl jedoch gerade muss erst auf dem Ausweichplatz gestapelt werden.
Eingangs hatten wir es erwähnt, viele Internetseiten beschäftigen sich mit dem Turmbau von Hanoi. Hier eine Auswahl:
de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi www.blinde-kuh.de/spiele/hanoi/ mond.at/mathe/hanoi.html
Um die Schreibarbeit in Grenzen zu halten, verwenden wir nun folgende Notation: Die Scheiben sein von der kleinsten zur größten von 1 bis n durchnummeriert. Die Ablageplätze tragen, wie bereits erwähnt, die Bezeichnungen A, B und C. Das Versetzen eines bestimmten Turmsegments auf einen Stapel drücken wir nun einfach durch die Nummer der jeweiligen Scheibe mit nachgestelltem Buchstaben des Zielstapels aus. Bei 1C wird also das kleinste Segment auf den Stapel C geschoben.
In dieser Schreibeweise lautet die Lösung für drei Steine von A nach B folgendermaßen: 1B, 2C, 1C, 3B, 1A, 2B, 1B. 7 Züge sind also für eine Turmversetzung nötig, wobei der erste Zug bereits zum späteren Standort des Turms führt.
Analog lässt sich das Spielchen für 4 und mehr Turmsegmente fortführen. Wobei sich die Schieberei großer Türme stets auf die kleiner Türme zurückführen lässt. Um beispielsweise einen 4er Turm zu versetzen, müssen wir zuerst seine Spitze - im Prinzip ein 3er Turm - an einen geeigneten Ausweichplatz - in unserem Fall C - manövrieren. Anschließend bewegen wir die größte Scheibe, das Fundament, an den gewünschten Ort, in unserem Fall B, und versetzen anschließend den 3er Turm auf dieses Fundament. Um einen 4er-Turm zu bewegen, müssen wir haben also zweimal einen 3er Turm verschieben und einen zusätzlichen Schritt für das Versetzen des Fundaments machen. Das gilt in gleicher Weise auch für alle größeren Türme, sodass man auf folgenden rekursiven Ausdruck für die Anzahl der Züge bei n Turmsegmenten kommt:
Z(n+1) = 2·Z(n)+1
Das Ganze lässt sich etwas handlicher auch durch eine Rekursionsformel ausdrücken:
Z(n) = 2n-1
Der Beweis kann beispielsweise durch vollständige Induktion erfolgen.
Wird mit einer ungeraden Anzahl von Turmsegmenten gespielt, dann darf der erste Zug bereits an den künftigen Standort führen. Ist die Zahl jedoch gerade muss erst auf dem Ausweichplatz gestapelt werden.
Eingangs hatten wir es erwähnt, viele Internetseiten beschäftigen sich mit dem Turmbau von Hanoi. Hier eine Auswahl:
de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi www.blinde-kuh.de/spiele/hanoi/ mond.at/mathe/hanoi.html
Das mathematische Problem stammt von Univ.-Prof. Dr. Gerd Baron und Dr. Richard F. Mischak. Weitere Aufgaben finden Sie auf den Seiten des Wettbewerbs Jagd auf Zahlen und Figuren. Die erzählerische "Verpackung" gestaltete Dr. Olaf Fritsche.
Schreiben Sie uns!