Tüftel & Rätselecke

Neues Rätsel: Eine Variante der Türme von Hanoi

(op) Zunächst bedanke ich mich an dieser Stelle herzlichst bei meinem Vorgänger Maik für die traumhaften Rätsel. Hoffen wir, dass ich die Rätseltradition ebenso erfolgreich weiterführen werde.

Das Türme-von-Hanoi-Problem dürfte aus der Praktischen Informatik I (oder Theoretischen Informatik I) bekannt sein [siehe Skript Praktische Informatik I von Prof. Schmidt-Schauß, Kapitel 4, Seite 1/2]: Gegeben sind n verschieden große Scheiben, die auf einem Stapel der Größe nach geordnet liegen. Ziel ist es, alle n Scheiben von diesem Anfangsstapel auf einen weiteren Stapel zu verschieben, wobei dazu nur ein weiterer Hilfsstapel zur Verfügung steht und immer nur die oberste Scheibe auf jedem Stapel einzeln verschoben werden darf. Außerdem dürfen auf jeder Scheibe nur kleinere Scheiben platziert werden. Per Induktion lässt sich leicht zeigen, dass das Problem für jedes n lösbar ist. Bei den buddhistischen Mönchen [Genauere Quelle nicht verfügbar] war nach der Verschiebung von 64 Scheiben das Ende der Welt gekommen. Leider (oder glücklicherweise für uns alle) ist die mimimale Anzahl an Scheibenverschiebungen bei diesem Unterfangen exponentiell in n [O(2n)], so dass wohl noch ein paar Millionen Jahre vergehen sollten, bis die Scheiben ihr Ziel erreichen.

Betrachten wir nun folgende Variante des Problems: Es sollen wieder n verschieden große Scheiben von einem Stapel auf einen anderen verschoben werden. Es gelten obige Einschränkungen bis auf die der Anzahl der Hilfsstapel. Gesucht ist die minimale Anzahl an Hilfsstapel in Abhängigkeit von n [z.B. O(log(n))], mit denen man das ganze mit linear [=O(n)] vielen Verschiebungen (ohne den Weg zu berücksichtigen) schaffen kann. Findet also einen Algorithmus, der besonders wenig Stapel benötigt. Experten können sich eine untere Schranke überlegen (und diese beweisen). Viel Spaß!