Der Turm von Hanoi

Kennt ihr den Turm von Hanoi? Es handelt sich hierbei um ein mathematisches Knobelspiel – und dieses Mal meine ich mit „Spiel“ wirklich ein Spiel im herkömmlichen Sinn, kein Spiel aus der Spieltheorie. Es geht darum, einen Turm, der aus Scheiben aufgebaut ist, die der Größe nach aufeinander gestapelt sind, an einen anderen Ort zu versetzen. Die Scheiben, aus denen der Turm besteht, haben in der Mitte ein Loch und sind auf einem Stab aufgefädelt. Zusätzlich zu diesem besetzten Stab gibt es noch zwei leere Stäbe daneben und nur diese dürfen beim Umsetzen des Turmes benutzt werden – er muss am Ende also auf einem der beiden anderen Stäbe wieder in seiner ursprünglichen Stapelfolge stehen. Beim Umsetzen gibt es zwei Regeln: Es darf immer nur eine Scheibe pro Zug versetzt werden und es darf nie eine größere auf eine kleinere Scheibe gelegt werden.

Eine Frage, die man sich nun stellen kann: Funktioniert das Umsetzen immer? Bei einem Turm, der nur aus einer Scheibe besteht, ist das, wie ihr euch sicher vorstellen könnt, kein Problem, genau so wenig bei einem Turm mit zwei Scheiben. Aber funktioniert das Umsetzen auch bei allen beliebigen Turmhöhen? Und falls ja, wie lange bzw. wie viele Züge braucht man dann dafür?

Um diese Fragen zu beantworten, fangen wir einfach mal mit ganz kleinen Türmen an.

  • Für einen Turm der Höhe 1 funktioniert das Umsetzen. Man braucht genau einen Zug, um die Scheibe vom ersten Stab auf einen der beiden anderen zu setzen (egal auf welchen). Ganz simpel.

An dieser Stelle ein kurzer Einschub: Es ist durchaus üblich, in der Mathematik mit solchen einfachen Fällen beim Betrachten eines Problems zu beginnen, auch wenn sie fast zu einfach erscheinen. Irgendwo muss man ja schließlich anfangen ;-)

  • Für einen Turm der Höhe 2 können wir uns das Umsetzen auch noch im Kopf vorstellen. Wir nehmen die obere (das ist die kleinere) der beiden Scheiben und legen diese auf einen der leeren Stäbe. Dann nehmen wir die größere Scheibe und legen sie auf den anderen leeren Stab. Zum Schluss kommt die kleine Scheibe auf die größere. Der Turm ist also umgesetzt und keine der Regeln dabei verletzt worden.
  • Für einen Turm der Höhe 3 schauen wir uns das Ganze einfach mal bildlich an. Hier sind die verschiedenen Züge der Reihe nach aufgemalt, wie das Umsetzen auf jeden Fall funktioniert. Innerhalb von sieben Zügen ist der Turm vom linken auf den mittleren Stab verschoben.

Diese Diashow benötigt JavaScript.

Natürlich könnte man das für die Höhen 4, 5, 6 und so weiter auch einfach probieren, um die oben gestellten Fragen zu beantworten, doch wir wollen jetzt schon etwas feststellen, wofür das Umsetzen des Turms mit Höhe 3 ausreicht.

Und zwar sehen wir nach dem dritten Schritt, dass auf dem rechten Stab ein korrekter Turm der Höhe 2 steht. Das ist auch notwendig, denn um die unterste (die größte) Scheibe zu versetzen, darf auf dieser selbst keine andere Scheibe mehr sein. Außerdem muss es einen freien Stab geben, auf den die größte Scheibe gesteckt werden kann, denn da sie die größte Scheibe ist, darf sie auf keiner anderen (egal auf welcher) Scheibe liegen.

hanoi4

Das heißt, um einen Turm der Höhe 3 zu verschieben, muss zunächst der Turm der Höhe 2, der zu Beginn auf der größten Scheibe liegt, komplett verschoben werden. Dann kann die größte Scheibe versetzt werden. Anschließend wandert der Höhe-2-Turm auf die umgesetzte, größte Scheibe.

Für einen Turm der Höhe 4 gilt dasselbe. Um die vierte Scheibe zu versetzen, muss sie erst komplett frei gemacht werden, das heißt, der auf ihr liegende Turm aus drei Scheiben muss komplett verschoben werden. Dann kommt die vierte Scheibe an die Reihe. Und schließlich wird der Höhe-3-Turm auf die versetzte, vierte Scheibe verschoben.

Für einen Turm der Höhe n gilt wiederum das Gleiche. Erst muss der Turm mit Höhe (n-1) umgesetzt werden, dann die unterste Scheibe (Scheibe n), dann nochmal der Turm mit Höhe (n-1), damit er wieder auf Scheibe n liegt.

Beim Umsetzen der um eins kleineren Türme gilt dabei immer, dass die größte Scheibe komplett ignoriert werden kann, denn alle Scheiben des um eins kleineren Turmes sind ja kleiner und können folglich auf die größte Scheibe gelegt werden. Man muss nur beachten, dass beim zweiten Mal, wenn der um eins kleinere Turm auf die größte Scheibe versetzt wird, die beiden Stäbe zum Versetzen (der leere und der, auf dem die größte Scheibe liegt) nicht mehr beliebig sind, denn der um eins kleinere Turm muss ja zum Schluss auf dem Stab mit der größten Scheibe landen. Beim ersten Mal, wenn der um eins kleinere Turm verschoben wird, sind die beiden übrigen Stäbe ja noch komplett leer und somit austauschbar.

Zusammengefasst benötigen wir für einen Turm der Höhe n also die folgende Anzahl an Zügen:

  • Erst muss der Turm mit Höhe (n-1) versetzt werden. Das schreiben wir mal als z(n-1) [z für Anzahl]
  • Dann wird mit einem Zug die Scheibe n versetzt.
  • Zum Schluss brauchen wir nochmal z(n-1)-viele Züge, um den Turm mit Höhe (n-1) auf die umgesetzte n-te Scheibe zu bringen.
  • Insgesamt sind das also z(n)=z(n-1)+1+z(n-1) Züge, oder etwas kürzer z(n)=2*z(n-1)+1.

Gut, aber wie viele Züge brauchen wir, um den Turm der Höhe (n-1) zu verschieben? Hier kommt die sogenannte Rekursivität der Formel bzw. der Überlegung ins Spiel. Denn für einen Turm der Höhe (n-1) gilt ja prinzipiell das Gleiche wie für den Turm mit Höhe n.

  • Erst wird der Turm mit Höhe (n-2) verschoben: z(n-2)-viele Züge
  • Dann wird die (n-1)-te Scheibe verschoben: 1 Zug
  • Dann nochmal z(n-2)-viele Züge, um den Höhe-(n-2)-Turm umzusetzen

So kann man immer weiter zurückgehen (deshalb die Bezeichnung rekursiv), bis man beim Turm der Höhe 1 angekommen ist, von dem man die Anzahl der Züge genau kennt.

Es ist also immer möglich, einen Turm zu versetzen, egal welche Höhe er hat. Zudem gibt die rekursive Formel auf jeden Fall eine obere Schranke für die minimale Anzahl an Zügen an, die für das Umsetzen benötigt wird. Reichen aber vielleicht auch weniger Züge als die Anzahl, die die rekursive Formel angibt? Die Frage beantwortet schon die Überlegung, wie die unterste Scheibe bewegt werden kann: Nur wenn der um eins kleinere Turm komplett auf einem anderen Stab liegt (dort darf er nur korrekt liegen), damit der dritte Stab leer ist, kann die größte Scheibe bewegt werden. Dies gilt aber für alle Türme mit beliebiger Höhe, also können es auch nicht weniger Züge sein als die, die die rekursive Formel angibt.

Es sind nun alle eingangs gestellten Fragen beantwortet. Jeder beliebige Turm kann versetzt werden und wir können die minimale Anzahl an Zügen berechnen, die dafür benötigt werden, wenn wir die Höhe des Turms kennen.

Das ist aber auch wieder ein kleines Hindernis. Eine rekursive Formel ist für Computer kein Problem, denn die können schnell rechnen, aber für einen Menschen ist sie etwas umständlich zu verwenden. Oder wie lange braucht ihr, um die Zugzahl anzugeben, die für das Versetzen eines Turms der Höhe 100 benötigt wird?

  • z(100)
  • = 2*z(99)+1
  • = 2*(2*z(98)+1)+1
  • = 2*(2*(2*z(97)+1)+1)+1
  • = …

Selbst wenn man die Formel bis zum Ende auflöst (dann, wenn für z(1)=1 eingesetzt werden kann), ist der entstandene Term doch recht lang … Das geht auch schneller, denn es gibt eine geschlossene Formel zur Berechnung der Zugzahl (im Gegensatz zur rekursiven Formel, die als nicht-geschlossen bezeichnet wird). Wie die lautet und warum sie korrekt ist, zeige ich euch aber ein andermal.

Bis demnächst also!

Michaela

Advertisements

4 Kommentare zu „Der Turm von Hanoi

Kommentar verfassen

Bitte logge dich mit einer dieser Methoden ein, um deinen Kommentar zu veröffentlichen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.