Das Problem der 100 Gefangenen – wer kann überleben?

Bild: “Cell – exhibition opening 14 Feb 2009” von FiDalwood. Lizenz: CC BY 2.0

Die Ausgangslage

Der Direktor eines Gefängnisses möchte 100 zum Tode verurteilten Insassen eine Überlebenschance geben. Dazu richtet er einen Raum ein, in dem sich ein Schrank mit ebenso vielen Schubladen wie Insassen befindet – also 100. Den Gefangenen wird je eine Zahl zwischen 1 und 100 zugeordnet und der Direktor legt in jede Schublade einen Zettel mit der Nummer eines Häftlings. Keine Zahl kommt dabei doppelt vor, es werden also alle Zahlen genau einmal verwendet. Die Schubladen sind ebenfalls bis 100 nummeriert – natürlich unabhängig von den sich darin befindlichen Zetteln.

Das Ziel: alle Gefangenen müssen den Zettel mit ihrer jeweiligen Nummer finden. Allerdings darf jeder Gefangene den Raum nur einzeln betreten und nicht mehr als 50 der 100 Schubladen öffnen. Sollte nur ein einziger die Aufgabe nicht erfüllen können, bleibt die Strafe bestehen. Die Gefangenen dürfen sich einmal vor der Aufgabe miteinander besprechen. Währenddessen findet jedoch kein Informationsaustausch statt.

Der Hintergrund

Dem Problem liegt eine zufällige Anordnung von Objekten in einer bestimmten Reihenfolge zugrunde – in der Mathematik nennt man das eine Permutation. Im Szenario sind die Insassen die Objekte, die in Form der nummerierten Zettel auf die 100 Schubladen verteilt werden. Dadurch entsteht eine Reihenfolge von Zahlen. In Schublade 1 befindet sich zum Beispiel die Nummer 3, in Schublade 54 die Nummer 9 und so weiter.

Da jeder Straftäter 50 von 100 Schubladen öffnen kann, hat jeder eine Chance von 50 %, seine Nummer zu finden. Gehen die Gefangenen ziellos vor – das heißt, sie wählen die Schubladen zufällig aus -, ergibt sich die Gesamtwahrscheinlichkeit ihres Überlebens aus dem Produkt der Einzelwahrscheinlichkeiten: man multipliziert also einhundert Mal 0,5 mit sich selbst. Das lässt sich schreiben als 0,5¹⁰⁰. Das Resultat ist eine 0 vor und eine 8 hinter dem Komma – mit 31 Nullen dazwischen. Ein Erfolg der Gruppe liegt folglich bei nahezu 0 % und ist damit fast unmöglich.

Die optimale Lösungsstrategie

Ein chaotisches Vorgehen bringt die Gefangenen einer Lösung des Problems demzufolge nicht sehr nahe. Das einzige Zugeständnis an die Gefangenen ist auch deren einzige Möglichkeit auf höhere Chancen: die gemeinsame Absprache im Vorfeld. Dazu bräuchten sie jedoch einen Plan, der eine große, wenn nicht gar die größte Überlebenswahrscheinlichkeit verspricht. Mathematiker haben bewiesen, dass die Zykel-Folgestrategie die optimale Lösung bietet.

Die zufällige Aufteilung der Zettel auf die Schubladen durch den Direktor ist also wie bekannt eine Permutation. Jede Permutation lässt sich ihrerseits in disjunktive und zyklische Zahlenreihen aufteilen. Diese Eigenschaft ist für die optimale Strategie elementar!

Die Gefangenen können nun die Permutation des Gefängnisdirektors (die Aufteilung der 100 Gefangenennummern auf die 100 Schubladen) in disjunkte Zyklen zerlegen, indem sie mit der Zahl beginnen, die auch die letzte Zahl sein soll: mit ihrer eigenen. Damit wird nicht nur eine bestimmte Folge an Schubladen vorgegeben, sondern es werden zusätzlich irrelevante Zyklen ausgeschlossen. Denn wählt man die Schublade mit der eigenen Nummer, endet die gewählte Zahlenreihe unweigerlich mit der eigenen Nummer – die Frage ist nur, ob innerhalb der maximal 50 möglichen Versuche.

Statt also wahllos – sprich zufällig – Schubladen zu öffnen, wird nun zuerst die Schublade untersucht, die die eigene Zahl trägt. Gefangener 1 öffnet also als Erstes Schublade 1. Findet er in dieser seine Nummer, war er erfolgreich und kann den Raum verlassen – der nächste Verurteilte ist an der Reihe. Findet er aber eine andere Nummer vor, öffnet er danach die Schublade mit dieser Nummer. Befindet sich also in Schublade 1 ein Zettel mit der Zahl 3, öffnet der Gefangene 1 die Schublade 3. Ist darin immer noch nicht die Zahl 1 zu finden, folgt er weiter dieser Strategie bis er die 1 gefunden hat oder die 50 Versuche aufgebraucht sind. Alle restlichen 99 Insassen gehen in gleicher Weise vor.

Durch dieses Vorgehen folgen sie jeweils zyklischen Permutationen: anhand der Schubladenzahlen und den darin liegenden Zetteln. Dieser Vorgang wiederholt sich im besten Falle hundertmal. So haben alle Teilnehmer ihre Nummer spätestens mit der 50. Schublade gefunden – solange jedoch kein Zyklus länger als 50 ist.

Die Chance

Es liegt auf der Hand, dass ein Zyklus nicht länger als 50 sein darf. Das heißt, während seines Versuches darf ein Verurteilter nicht mehr als 50 Schubladen öffnen müssen, um seine Nummer zu finden. Andernfalls wäre die ganze Gruppe gescheitert.

Bei der Berechnung der Überlebenschance mit der Zykel-Folgestrategie nimmt man diese Prämisse als Ausgangspunkt, da die Wahrscheinlichkeit eines Zyklus länger als 50 mit der Erfolgswahrscheinlichkeit gleichzusetzen ist. Über mehrere Schritte lässt sich darauf aufbauend die Wahrscheinlichkeit berechnen.

Trotz dessen, dass die Zykel-Folgestrategie die bestmögliche ist, verspricht sie den Gefangenen keine sichere Aussicht auf Rettung. Das Ergebnis ist in Anbetracht der geringen Chancen ohne jedwede Strategie dennoch bemerkenswert: die Wahrscheinlichkeit zu überleben beträgt immerhin rund 31 %.

Die enorm gestiegenen Erfolgsaussichten basieren auf mehreren Aspekten. Zunächst können die Gefangenen einem klaren Prozedere folgen und müssen nicht frei wählen – das minimiert den Zufall deutlich. Beispielsweise dadurch, dass die erste Schublade vorgegeben wird und sich damit jede weitere Schublade aus der vorherigen ergibt – aber vor allem da der Gefangene sich bei der Suche in einem dem für ihn relevanten Zyklus befindet. Denn das bedeutet, andere Gefangene aus diesem Zyklus haben den gleichen Erfolg oder Misserfolg wie der Teilnehmer, der zuerst eine Zahl aus diesem Zyklus zieht. Führt unser Beispiel-Zyklus der Länge 4 (1 3 8 5) für den Gefangenen 1 zum Erfolg, gilt das Gleiche für die Verurteilten 3, 8 und 5. Die Ergebnisse sind also abhängig voneinander.

Es versteht sich von selbst, dass die Methode darüber hinaus das wiederholte Öffnen von Schubladen verhindert – in jedem Zyklus befindet sich jede Zahl nur einmal.