mini|hochkant=1.5|Jeder Gefangene muss seine Nummer in einer von 100 Schubladen finden, darf aber nur 50 der Schubladen öffnen Das Problem der 100 Gefangenen ist ein mathematisches Problem aus der Wahrscheinlichkeitstheorie und Kombinatorik. Bei diesem Problem muss jeder von 100 durchnummerierten Gefangenen zum Überleben aller seine eigene Nummer in einer von 100 Schubladen wiederfinden, wobei jeder Gefangene nur 50 der Schubladen öffnen und mit den anderen Gefangenen nicht kommunizieren darf. In dieser zunächst aussichtslos erscheinenden Situation gibt es dennoch eine Strategie, die den Gefangenen eine gute Überlebenschance gibt. Das Problem wurde erstmals 2003 vom dänischen Informatiker Peter Bro Miltersen vorgestellt.

Problemstellung Für das Problem der 100 Gefangenen finden sich in der Literatur unterschiedliche Darstellungen. Die folgende Formulierung des Problems basiert auf einer Beschreibung von Philippe Flajolet und Robert Sedgewick:

„Der Leiter eines Gefängnisses gibt 100 zum Tode verurteilten Gefangenen mit den Nummern von 1 bis 100 eine letzte Chance. In einem Raum befindet sich ein Schrank mit 100 Schubladen. Der Gefängnisleiter legt in jede Schublade die Nummer genau eines Gefangenen in zufälliger Reihenfolge und schließt die Schubladen daraufhin. Die Gefangenen betreten den Raum der Reihe nach. Jeder Gefangene darf 50 Schubladen in einer beliebigen Reihenfolge öffnen und muss sie danach mit ihrem Inhalt wieder schließen. Finden dabei alle Gefangenen ihre eigene Nummer in einer der Schubladen, werden die Gefangenen begnadigt. Findet irgendein Gefangener seine Nummer nicht, müssen alle Gefangenen sterben. Bevor der erste Gefangene den Raum betritt, dürfen sich die Gefangenen beraten, danach ist jedoch keinerlei Kommunikation mehr möglich. Was ist für die Gefangenen die beste Strategie?“

Wählt jeder Gefangene seine 50 Schubladen zufällig aus, dann beträgt die Wahrscheinlichkeit, dass ein einzelner Gefangener seine Nummer findet, 50 Prozent. Die Wahrscheinlichkeit, dass alle Gefangenen ihre Nummern finden, ist dann gleich dem Produkt der Einzelwahrscheinlichkeiten und somit 0,5100 ≈ 10−30,1 ≈ 8 · 10−31 = 0,0000000000000000000000000000008, d. h. mit weniger als 1 : 1 Quintillion verschwindend gering. Die Situation erscheint aussichtslos für die Gefangenen.

Lösung

Strategie Es gibt jedoch eine Strategie, mit der die Gefangenen eine Überlebenswahrscheinlichkeit von etwas mehr als 30 % erhalten. Der Schlüssel zum Erfolg liegt darin, dass die Gefangenen nicht vorab entscheiden müssen, welche Schubladen sie öffnen wollen. Jeder Gefangene kann sich bei der Entscheidung, welche Schublade er als Nächstes öffnet, auf die Informationen stützen, die er aus den von ihm bereits geöffneten Schubladen erhalten hat. Eine weitere wichtige Beobachtung ist, dass dabei der Erfolg eines Gefangenen nicht unabhängig vom Erfolg der anderen Gefangenen ist.

Zunächst werden die Schubladen von den Gefangenen gedanklich mit den Zahlen von 1 bis 100 durchnummeriert, zum Beispiel zeilenweise von links oben nach rechts unten. Die Strategie lautet nun wie folgt:

Jeder Gefangene öffnet als erste die Schublade, die mit seiner eigenen Nummer gedanklich nummeriert ist. Befindet sich seine Nummer in dieser Schublade, dann ist er mit der Suche fertig und war erfolgreich. Andernfalls befindet sich in der Schublade die Nummer eines anderen Gefangenen und er öffnet als nächste die Schublade mit dieser Nummer. Der Gefangene wiederholt die Schritte 2 und 3 so lange, bis er seine eigene Nummer gefunden hat oder bis er 50 Schubladen geöffnet hat.

Ohne die Beschränkung auf 50 Schubladen würde sich bei diesem Vorgehen in jedem Fall ein Zyklus von Nummern ergeben, der mit der Nummer des Gefangenen beginnt und endet. Falls dieser Zyklus aus bis zu 50 Nummern besteht, war der Gefangene erfolgreich; andernfalls ist er gescheitert.

Beispiele Dass diese Strategie erfolgversprechend ist, soll an folgendem Beispiel mit acht Gefangenen und Schubladen, wobei jeder Gefangene vier Schubladen öffnen darf, illustriert werden. Der Gefängnisleiter habe die Nummern der Gefangenen wie folgt auf die Schubladen verteilt:

Nummer der Schublade   1     2     3     4     5     6     7     8   Nummer des Gefangenen 7 4 6 8 1 3 5 2

Die Gefangenen handeln nun wie folgt:

Der Gefangene 1 öffnet Schublade 1 und findet dort die Nummer 7. Daraufhin öffnet er Schublade 7 und findet dort die Nummer 5. Nun öffnet er Schublade 5, findet dort seine eigene Nummer 1 und ist somit erfolgreich. Der Gefangene 2 öffnet die Schubladen 2, 4 und 8 in dieser Reihenfolge, wobei er in Schublade 8 seine eigene Nummer 2 findet. Der Gefangene 3 öffnet die Schubladen 3 und 6, wo er bereits seine eigene Nummer findet. Der Gefangene 4 öffnet die Schubladen 4, 8 und 2, wo er dann seine eigene Nummer findet. Dies kann auch aus den Informationen, die der zweite Gefangene erhalten hat, abgeleitet werden. Dass auch die Gefangenen 5 bis 8 ihre Nummern finden werden, kann ebenfalls aus den Informationen der ersten drei Gefangenen abgeleitet werden.

Die Gefangenen werden in diesem Fall also erfolgreich alle ihre Nummern finden. Allerdings ist dies nicht immer der Fall. Als zweites Beispiel habe der Gefängnisleiter die Nummern nun wie folgt verteilt:

Nummer der Schublade   1     2     3     4     5     6     7     8   Nummer des Gefangenen 3 1 7 5 8 6 4 2

In diesem Fall öffnet der Gefangene 1 der Reihe nach die Schubladen 1, 3, 7 und 4, wo er erfolglos abbrechen muss. Bis auf den Gefangenen 6, der direkt seine Nummer findet, wären auch alle anderen Gefangenen erfolglos.

Permutationsdarstellung

Die von dem Gefängnisleiter vorgenommene zufällige Zuordnung von Gefangenen zu Schubladen kann mathematisch als Permutation der Zahlen von 1 bis 100 beschrieben werden. Eine solche Permutation ist eine eindeutig umkehrbare Abbildung der Menge der natürlichen Zahlen von 1 bis 100 auf sich selbst. Eine Folge von Zahlen, die durch wiederholte Anwendung einer Permutation entsteht und am Ende zur Ausgangszahl zurückkehrt, heißt Zyklus der Permutation. Jede Permutation zerfällt in disjunkte Zyklen bestehend aus unterschiedlichen Zahlen und kann durch ihren Zyklentyp beschrieben werden. Die erste Beispielpermutation des vorangegangenen Abschnitts kann in Zyklenschreibweise durch

dargestellt werden und besteht damit aus zwei Zyklen der Länge drei und einem Zyklus der Länge zwei. Die zweite Beispielpermutation hat die Darstellung

und besteht aus einem Zyklus der Länge sieben und einem der Länge eins. Die Zyklendarstellung ist dabei nicht eindeutig, denn ein Zyklus der Länge kann durch Wahl jeweils einer anderen Startzahl auf verschiedene Weisen geschrieben werden. Jeder Gefangene folgt beim Öffnen der Schubladen nun einem Zyklus, der mit seiner eigenen Nummer endet. Bei acht Gefangenen ist diese Zyklusfolgestrategie für eine beliebige Permutation genau dann erfolgreich, wenn die Länge des längsten Zyklus der Permutation höchstens vier ist. Besitzt die Permutation nämlich einen Zyklus der Länge fünf oder größer, dann werden alle Gefangenen, deren Nummern in diesem Zyklus liegen, nach vier Schritten noch nicht bei ihrer eigenen Nummer angelangt sein.

Erfolgswahrscheinlichkeit mini|hochkant=1.5|Wahrscheinlichkeits­verteilung der Länge des längsten Zyklus einer zufälligen Permu­tation der Zahlen von 1 bis 100. Die grüne Fläche entspricht der Überlebens­wahrschein­lichkeit der Gefangenen.

Übertragen auf das ursprüngliche Problem der 100 Gefangenen werden diese mit ihrer Strategie genau dann erfolgreich sein, wenn der längste Zyklus der Permutation höchstens die Länge 50 besitzt. Die Wahrscheinlichkeit, dass die Gefangenen überleben, ist somit gleich der Wahrscheinlichkeit, dass eine zufällige Permutation der Zahlen von 1 bis 100 keinen Zyklus mit einer Länge größer als 50 enthält. Diese Wahrscheinlichkeit wird im Folgenden ermittelt.

Zunächst kann eine Permutation der Zahlen von 1 bis 100 maximal einen Zyklus mit einer Länge besitzen. Dabei gibt es genau Möglichkeiten, die Zahlen eines solchen Zyklus auszuwählen (siehe Kombination ohne Wiederholung). Diese Zahlen lassen sich innerhalb des Zyklus auf Weisen anordnen (siehe Permutation ohne Wiederholung), denn es gibt Möglichkeiten, die Startzahl des Zyklus auszuwählen. Die verbleibenden Zahlen können schließlich auf Arten angeordnet werden. Damit ist die Anzahl der Permutationen der Zahlen von 1 bis 100 mit einem Zyklus der Länge gleich

.

mini|hochkant=1.5|Die harmonischen Zahlen ergeben sich näherungs­weise als Fläche unter der Hyperbel und lassen sich somit durch die Logarithmus­funktion approximieren.

Die Wahrscheinlichkeit, dass eine (gleichverteilt) zufällige Permutation keinen Zyklus mit einer Länge größer als 50 aufweist, ist mit der Formel für die Gegenwahrscheinlichkeit und der Laplace-Formel demnach

,

wobei die -te harmonische Zahl ist. Die Wahrscheinlichkeit, dass die Gefangenen überleben, beträgt mit der Zyklusfolgestrategie demnach erstaunliche 31 %.

Grenzwertbetrachtung mini|hochkant=1.5|Überlebens­wahrscheinlichkeit in Abhängig­keit von der Zahl der Gefangenen

Werden allgemein statt 100 Gefangenen Gefangene betrachtet, wobei eine beliebige natürliche Zahl ist, dann beträgt die Überlebenswahrscheinlichkeit mit der Zyklusfolgestrategie

.

Mit der Euler-Mascheroni-Konstante gilt nun für

,

wodurch sich eine asymptotische Überlebenswahrscheinlichkeit von

ergibt. Da die Folge der Wahrscheinlichkeiten monoton fallend ist, überleben die Gefangenen mit der Zyklusfolgestrategie bei einer beliebigen Anzahl von Gefangenen in mehr als 30 % der Fälle.

Optimalität Eugene Curtin und Max Warshauer gaben 2006 einen Beweis für die Optimalität der Zyklusfolgestrategie an. Der Beweis basiert auf der Herstellung einer Äquivalenz zu einem verwandten Problem, bei dem sich alle Gefangenen in dem Raum aufhalten und die Auswahl der Schubladen beobachten dürfen. Diese Äquivalenz beruht auf einer Korrespondenz zwischen der (normalisierten) Zyklenschreibweise und der Tupeldarstellung von Permutationen. In dem zweiten Problem ist die Erfolgswahrscheinlichkeit unabhängig von der gewählten Strategie und gleich der Erfolgswahrscheinlichkeit beim Ausgangsproblem mit der Zyklusfolgestrategie. Nachdem eine beliebige Strategie beim Ausgangsproblem auch in dem zweiten Problem eingesetzt werden kann, dort aber keine höhere Erfolgswahrscheinlichkeit besitzt, muss die Zyklusfolgestrategie optimal sein.

Geschichte Das Problem der 100 Gefangenen wurde erstmals 2003 von dem dänischen Informatiker Peter Bro Miltersen betrachtet und mit Anna Gál in einem Konferenzbeitrag zum 30. International Colloquium on Automata, Languages and Programming (ICALP) veröffentlicht. In ihrer Version färbt Spieler A (der Gefängnisleiter) Zettel mit den Namen der Spieler von Team B (den Gefangenen) rot oder blau und steckt diese in jeweils einen Kasten. Jeder Spieler von Team B muss, damit das Team gewinnt, die Farbe seines Zettels korrekt erraten, nachdem er die Hälfte der Kästen geöffnet hat. Anfänglich nahm Miltersen an, dass die Gewinnwahrscheinlichkeit mit der Anzahl der Spieler sehr schnell nach null strebt. Sven Skyum, ein Kollege Miltersens an der Universität Aarhus, machte ihn jedoch auf die Zyklusfolgestrategie aufmerksam. Diese Strategie zu finden, wurde in dem Konferenzbeitrag als Übungsaufgabe offengelassen. Der Beitrag wurde mit dem Best Paper Award ausgezeichnet.