Fassen Sie einen Stapel von \(n\) Scheiben als untere Scheibe plus die oberen \(n-1\) Scheiben auf und tun Sie so, als wären die \(n-1\) Scheiben erst einmal kein Problem.

Wir folgen sogleich dem Tipp: Angenommen, \(z_n\) sei die optimale Anzahl der Züge für das Spiel mit \(n\) Scheiben. Nun fragen wir uns, was geschehen muss, wenn stattdessen \(n+1\) Scheiben von links nach rechts bewegt werden sollen. Dazu verlagern wir erst einmal ordnungsgemäß die \(n\) oberen der \(n+1\) Scheiben von links zur Mitte (mit dem rechten Stapel als Zwischenspeicher) und brauchen dazu \(z_n\) Züge (welche Zahl das auch immer sein mag). Mit dem nächsten Zug legen wir die unterste Scheibe von links nach rechts. Dann brauchen wir noch einmal \(z_n\) Züge, um die \(n\) Scheiben von der Mitte nach rechts zu bringen, und wir sind fertig.

Es gibt also eine Rekursionsformel: \(z_{n+1}=2z_n+1\), die uns angibt, wie wir von einem \(n\) zum nächsten kommen. Da wir für eine Scheibe nur einen Zug benötigen, können wir also mit 1 anfangen und rechnen einfach weiter:

Wenn jetzt jemand wissen will, wie viele Züge man für 100 Scheiben braucht, könnte man das in 99 Zwischenschritten ausrechnen, was etwas lästig wäre, wenn man die anderen Zahlen dazwischen gar nicht wissen will. Geht es auch auf einen Schlag, also mit Vermeidung der rekursiven Ausrechnung?

Die Zahlen sehen so aus, als seien sie einfach immer um 1 kleiner als die ganzzahligen Potenzen von 2, also 2 4 8 16 32 usw. Das könnte aber Zufall sein, selbst wenn wir die Folge noch etwas weiter testen und bestätigt finden.

Die Vermutung ist also: \(z_n =^? 2^n-1\).

Verdoppeln wir das und addieren 1, wie es die Rekursionsformel verlangt, bekommen wir tatsächlich \(2\cdot(2^n-1)+1=2^{n+1}-1\).

Diesen Schluss ("von \(n\) auf \(n+1\)") können wir nun beliebig oft anwenden, ohne das jedesmal neu hinzuschreiben. Wenn die Vermutung also für eine bestimmte ganze Zahl \(n\) stimmt, dann auch für jede größere ganze Zahl ("vollständige Induktion" genannt, gemeint: Beweis für abzählbar unendlich viele Zahlen).

Aus dem Schluss von von \(n\) auf \(n+1\) folgt aber nicht unbedingt, dass die Aussage überhaupt für irgendein \(n\) gilt, denn er sagt erst einmal: Wenn sie für ein ganzes \(n\) gilt, dann auch für jede größere ganze Zahl.

In unserem Fall ist es aber ganz einfach, auch die notwendige "Verankerung" zu sehen: Für \(n=1\) ist \(z_n=1\), einerseits weil \(2^1-1=1\) ist und andererseits weil wir wissen, dass wir für eine Scheibe einen Zug brauchen, also dass \(z_1=1\) ist.

Nun können wir ohne Zwischenschritte ausrechnen, wie viele Züge man für 100 Scheiben braucht, nämlich 2¹⁰⁰-1. Auch ohne Rechenmaschine kann man das zumindest schätzungsweise in eine Dezimalzahl umrechnen:

Da 2¹⁰ = 1024 nicht viel mehr als 10³ = 1000 ist, ist 2⁶⁴ ungefähr 16\(\cdot\)1000⁶ = über 10¹⁹, auf jeden Fall also eine Dezimalzahl mit mindestens 19 Ziffern.

Mit Logarithmen oder einer Rechenmaschine geht das noch etwas genauer, was aber hier nicht so wichtig ist.

Das 1883 von Edouard Lucas (unter dem Pseudonym M. Claus, bei dem die 5 Buchstaben umgestellt sind) veröffentlichte Spiel wird bei uns meistens "Türme von Hanoi" genannt wird. 1884 hat M. de Parville in "La Nature" eine Legende beschrieben:

Im Tempel von Benares (also nicht in Vietnam, sondern in Indien) gibt es auf einer Messingplatte drei Diamantnadeln, zwischen denen seit der Erschaffung der Welt von jeweils einem diensthabenden Priester 64 goldene Scheiben gewechselt werden. Wenn diese Aufgabe beendet ist, wird der Tempel zu Staub zerfallen, und die Welt wird mit einem Donnerschlag untergehen.

Das ist vielleicht eine etwas optimistische Prognose, denn die Zahl der Sekunden seit dem Urknall hat nur 17 bis 18 Ziffern. Wenn man statt 64 Scheiben 100 annimmt, hat die Welt sogar noch das Billionenfache ihres bisherigen Alters vor sich.

Reizvoll finde ich an dieser (also keineswegs besonders alten!) Legende, dass hier die kombinatorischen Zahlen die astronomischen bei Weitem übertreffen, anders: Wer riesige Zahlen "astronomisch" nennt, hat keine Ahnung von Kombinatorik.

Das Rezept zum Selberspielen lautet: Wenn Sie einen (oberen) Teilstapel mit ungerader Scheibenanzahl von einem Ort zu einem anderen bringen wollen, fangen Sie damit an, dass Sie die oberste Scheibe zum Ziel des ganzen Teilstapels bringen, bei einer ungeraden Scheibenzahl jedoch zum Ausweichquartier. Man kann dann zwar immer noch die Übersicht verlieren, verläuft sich aber deutlich seltener.

Ian Stewart schlägt in der "Reise nach Pentagonien" eine graphentheoretische Lösung vor: Alle nach den Spielregeln möglichen Zustände des Spieles – auch die unzweckmäßigen – werden als Knoten dargestellt, die erlaubten Züge zwischen ihnen als Linien. Für sehr wenige Scheiben sind diese Graphen sehr einfach, für jeweils eine Scheibe mehr verdreifacht sich die Figur, zusätzlich kommen die drei Verbindungen zwischen den drei Teilen. Alle Wege in diesen Graphen sind mögliche Spiele, aber nur die kürzesten Verbindungen zwischen zwei Ecken sind optimale Spiele mit der jeweiligen Mindestzahl von Zügen.

Für 3 Scheiben sieht der Graph so aus (denken Sie sich Verbindungslinien zwischen unmittelbar benachbarten Kreisen):

Die Buchstaben kennzeichnen hier nicht die Scheiben, sondern die Stapel! Und zwar bezeichnen sie von rechts nach links die Positionen der Scheiben von der größten zur kleinsten. Die Wege mit 7 Schritten auf den Außenseiten sind optimale Spiele, alle anderen Wege sind Umwege.

Für 5 bzw. 7 Scheiben sind die Graphen entsprechend umfangreicher:

Lässt man die Zahl der Scheiben unbegrenzt wachsen und normiert die Figur auf eine endliche Größe, so strebt sie zum Sierpinski-Dreieck.

Ich muss zugeben, dass diese Beziehung zur fraktalen Geometrie so etwas wie das Sahnehäubchen ist auf einem Spiel, das eines der schönsten Musterbeispiele für eines der elegantesten Beweisverfahren ist und außerdem noch (mit oder ohne Verbrämung mit Legenden und Weltuntergang) die ungeheuren Zahlengrößen aufzeigt, die die geometrische Folge bietet. Außerdem ist es natürlich ein schönes Konzentrationsspiel und für den Anfänger ein Knobelspiel, bei dem keineswegs von vornherein die Lösbarkeit klar ist.