Turm von Hanoi

Seite vorlesen


Bringe den Turm auf einen anderen Stift! Bewege immer nur eine Scheibe und lege niemals eine größere auf eine kleinere! Mit wie vielen Zügen schaffst du es? Geht es mit noch weniger Zügen?

WORUM GEHT ES?
Einer hinduistischen Sage nach befindet sich im Tempel von Benares ein Spiel mit 64 goldenen Lochscheiben unterschiedlicher Größe. Neben diesen Scheiben gibt es drei Stifte, auf die die Platten geschoben werden können. Zu Beginn sind alle Scheiben der Größe nach auf einem Stift angeordnet – beginnend mit der größten. Weiter heißt es in der Sage, gelänge es diesen Turm unter Beachtung der gegebenen Regeln auf einen der anderen beiden Stifte umzuschichten, würde die Welt untergehen. Das allerdings würde ca. 600 Milliarden Jahre dauern, selbst wenn man jede Sekunde eine Scheibe bewegt. In der PHÄNOMENTA wird allerdings „nur“ mit fünf Scheiben gespielt, so dass man das Spiel in angemessener Zeit zu Ende bringen kann.

Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel. Das Spiel besteht aus drei Stäben A, B und C, auf die mehrere gelochte Scheiben in verschiedenen Größen gelegt werden. Zu Beginn liegen alle Scheiben auf Stab A der Größe nach geordnet. Die größte Scheibe ist dabei ganz unten und die kleinste oben. Ziel des Spiels ist es, den kompletten Scheibenstapel von A nach C zu versetzen. Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Stab der Größe nach geordnet.

WESHALB IST DAS SO?
Die Lösungsstrategie lässt sich rekursiv entwickeln, das heißt, hat man den ersten Fall gelöst, können alle weiteren Fälle auf den ersten zurückgeführt werden. Fangen wir mit zwei Scheiben an. Um diese von einem Platz auf einen anderen zu transportieren, benötigt man drei Züge. Diese sehen wie folgt aus: Zuerst bewegt man die kleinere Scheibe auf einen der anderen Plätze. Dann wird die größere Scheibe auf den freien Platz gesetzt und zum Schluss die kleinere Scheibe wieder auf die größere. Hat man nun drei Scheiben, muss zunächst der Teilturm aus zwei Scheiben auf einen der freien Plätze verschoben werden. Dafür benötigt man drei Züge. Dann setzt man die größte Scheibe auf den letzten verbliebenen freien Platz. Schließlich muss man den Teilturm wieder auf die größte Scheibe bauen, wofür man weitere drei Züge benötigt. Es ergeben sich also insgesamt 3 + 1 + 3 = 2 . 3 + 1 = 7 = 23 – 1 Züge. Führt man alles mit vier Scheiben durch, kommt man auf 7 + 1 + 7 = 2 . 7 + 1 = 15 = 24 – 1 Schritte. Bei fünf Scheiben (wie hier in der PHÄNOMENTA) sind es dann 15 + 1 + 15 = 31 = 25 – 1 Schritte, die man mindestens braucht. Man gelangt schließlich zu der folgenden allgemeinen Formel an = 2n – 1, mit der man die Anzahl der Schritte bestimmen kann. Dabei steht n für die Anzahl der benutzten Scheiben. Setzt man zum Beispiel für n zehn ein, ergibt sich a10 = 210 – 1 =1023 für die Anzahl der Spielzüge, die bei optimaler Strategie nötig, sind um alle Scheiben in richtiger Reihenfolge auf einen anderen Platz zu stapeln.

Alltagsbezug
Ein schönes Beispiel für große Zahlen sind die Adressen im Internet. Wir Menschen sind es gewohnt, mit einem Zahlensystem zu rechnen, das auf der 10 basiert, vermutlich weil wir 10 Finger haben. Wenn man alle durchgezählt hat, merkt man sich das (man nennt das Zehner-Übergang) und dann fängt man wieder bei eins an zu zählen. Hat man das z.B. 4 mal gemacht, lautet die Zahl 40: Man hat 4 mal bis 10 gezählt. Ein Computer arbeitet mit nur zwei Zahlen, nämlich 0 und 1, er verwendet das Dualsystem. Er hat dann allerdings bei jeder zweiten Zahl einen „Zehnerübergang“, besser „Zweierübergang“, dafür sind die beiden Zahlen aber sehr leicht technisch darstellbar: AN und AUS.

Man kann die Stellen großer Zahlen einfacher darstellen, statt 1000 mit drei Nullen zu schreiben kürzt man ab auf 10³ (gelesen: zehn hoch drei). Bei kleinen Zahlen scheint das zunächst komplizierter, denn auch mit sechs Nullen bei 1.000.000 kommt man im Alltag noch zurecht. Aber dann beginnt man die Nullen zu zählen. Deshalb wird die Abkürzung 106 für 1.000.000 schon bequem, für größere Zahlen gilt das erst recht. Im dualen Zahlensystem schreibt man entsprechend: 2², 2³ usw. Früher basierten die Rechner auf Zahlen, die 8 Stellen hatten, nämlich 8 Bit oder 28.

Um eine Internetadresse darzustellen, nahm man einfach 4 solcher 8-Bit-Zahlen hintereinander: 28 mal 28 mal 28 mal 28. Dies war die höchste Zahl der darstellbaren Internetadressen. Man kann das auch einfach ausrechnen: Wenn man 28 mal 28 mal 28 mal 28 rechnen will, braucht man nach den Regeln der Potenzrechnung nur die Exponenten, also die 8-er zu addieren und die Basis beibehalten: also 232. Im Zehnersystem lautet die Zahl: 4.294.967.296, also mehr als 4 Milliarden.

Mittlerweile sind das zu wenig mögliche IP-Adressen (auch moderne internetfähige Kühlschränke bekommen eine!). Also hat man einfach die Anzahl der Blöcke und die Anzahl der Stellen verdoppelt: also 216 und das 8-mal mit sich selbst multipliziert. Dies ergibt nun 2128 . Das Ergebnis ist im Zehnersystem eine Zahl, die mit den Ziffern 3 und 4 beginnt und 37 weitere Stellen hat. Diese Zahl ist in normaler Schreibweise nicht mehr vernünftig darstellbar.

Mit der Anzahl von Kombinationen verhält es sich ähnlich. Denkt man an einen PKW, der mit 5 verschiedenen Motoren und in 5 Farben ausgeliefert wird, kann man 5 mal 5, also 5² = 25 verschiedene Modelle liefern. Ist zusätzlich noch die Wahl aus 5 verschiedenen Radios möglich, sind das schon 5³ (Motor, Farbe, Radio), also 125 verschiedene Modelle. Kommen jetzt noch 5 Reifengrößen, je 5 verschiedene Felgen, Sitzbezüge usw. hinzu, wird die Zahl schnell riesengroß. Theoretisch kann man einen VW Golf so zusammenstellen, dass niemals einer dem anderen gleicht. Deshalb werden viele Ausstattungen zu Paketen zusammengefasst, um die potentielle Vielfalt wenigstens etwas zu verringern.