Turm von Hanoi

Der Turm von Hanoi ist ein klassisches Geduldspiel. In seiner einfachsten Form besteht der Turm aus einem Pfosten, auf den 3 Kreisscheiben gesteckt sind, und aus zwei freien Pfosten. Der Turm soll auf einem neuen Pfosten aufgebaut werden. Bei jedem Schritt darf nur eine Scheibe umgelegt werden, und es darf nie eine grössere Scheibe auf eine kleinere gelegt werden. Der dritte Pfosten dient als Zwischenstation.

Geschichte

Das Spiel wird 1883 vom französischen Mathematiker Edouard Lucas (d'Amiens) von der Sekundarschule Saint Louis erfunden. Er veröffentlicht es zunächst unter dem Pseudonym "Professor N. Claus de Siam" von der Sekundarschule von "Li-Sou-Stian". Als pseudohistorische Einkleidung erfindet Lucas die Geschichte der indischen Mönche im grossen Tempel zu Benares, die den aus 64 goldenen Scheiben gebauten Turm von Brahma versetzen müssen. Wenn sie damit fertig sind, wird der Tempel zerstört werden, und der Weltuntergang wird kommen. Theoretisch benötigen sie für diese Aufgabe mindestens 2^64 – 1 Züge, eine 20-stellige Zahl. Wird pro Sekunde eine Scheibe umgelegt, so dauert der ganze Vorgang mehrere hundert Milliarden Jahre.

Mathematik

In seiner Einfachheit ist der Turm von Hanoi ein schönes Beispiel für ein Problem, das rekursiv gelöst werden kann. Kennt man nämlich die Lösung für n Scheiben, so kann man die Lösung für n + 1 Scheiben konstruieren. Das Problem ist für eine beliebige Anzahl Scheiben lösbar. Für n Scheiben sind mindestens 2^n – 1 Schritte nötig.

Die Zahlen 2^n – 1 heissen Mersenne-Zahlen. Sie sind von grossem Interesse, weil man unter ihnen, heute mit Hilfe des Computers, die grössten bekannten Primzahlen gefunden hat. Die Frage, ob sie eine unendliche Folge von Primzahlen liefern, ist noch nicht beantwortet.