Problem der 100 Gefangenen

Das Problem der 100 Gefangenen ist ein mathematisches Problem aus der Wahrscheinlichkeitstheorie und Kombinatorik. Bei diesem Problem müssen 100 Gefangene um zu überleben ihre Nummern in einer von 100 Schubladen wiederfinden, wobei jeder Gefangene nur 50 der Schubladen öffnen darf und mit den anderen Gefangenen nicht kommunizieren darf. In dieser zunächst aussichtslos erscheinenden Situation gibt es überraschenderweise eine Strategie, die den Gefangenen dennoch eine gute Überlebenschance gibt. Das Problem wurde erstmals 2003 von dem 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 stammt 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 wieder schließen. Finden dabei alle Gefangenen ihre eigene Nummer in einer der Schubladen, werden die Gefangenen begnadigt. Findet nur ein 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 %. Die Wahrscheinlichkeit, dass alle Gefangenen ihre Nummern finden, ist dann gleich dem Produkt der Einzelwahrscheinlichkeiten und somit 2^-100 ≈ 0,0000000000000000000000000000008, also verschwindend gering. Die Situation erscheint aussichtslos für die Gefangenen.

Lösung

Strategie

Überraschenderweise gibt es eine Strategie, mit der die Gefangenen eine Überlebenswahrscheinlichkeit von über 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 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.

Zur Beschreibung der Strategie werden nicht nur die Gefangenen, sondern auch die Schubladen von 1 bis 100 der Reihe nach durchnummeriert. Die Strategie lautet nun wie folgt:

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

Bei diesem Vorgehen ist sichergestellt, dass ein Gefangener jedes Mal, wenn er eine Schublade öffnet, entweder seine eigene Nummer oder eine noch nicht gesehene Nummer eines anderen Gefangenen vorfindet.

Beispielfälle

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 war auch bereits dem zweiten Gefangenen bekannt.
• 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 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

Graphdarstellung der Permutationen (1 7 5)(2 4 8)(3 6) und (1 3 7 4 5 8 2)(6)

Die von dem Gefängnisleiter vorgenommene 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 in 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 und kann durch ihren Zykeltyp beschrieben werden. Die erste Beispielpermutation des vorangegangenen Abschnitts kann in Zykelschreibweise durch

$(1~7~5)(2~4~8)(3~6)$

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

$(1~3~7~4~5~8~2)(6)$

und besteht aus einem Zyklus der Länge sieben und einem der Länge eins. Die Zykeldarstellung ist dabei nicht eindeutig, denn ein Zyklus der Länge $l$ kann durch Wahl jeweils einer anderen Startzahl auf $l$ verschiedene Weisen geschrieben werden. Jeder Gefangene folgt beim Öffnen der Schubladen nun einem Zyklus, der mit seiner eigenen Zahl endet. Bei acht Gefangenen ist diese Zykelfolgestrategie 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 mehr, dann werden alle Gefangenen, deren Nummern in diesem Zyklus liegen, nach vier Schritten noch nicht bei ihrer eigenen Nummer angelangt sein.

Erfolgswahrscheinlichkeit

Wahrscheinlichkeits­verteilung der Länge des längsten Zyklus einer zufälligen Permutation der Zahlen von 1 bis 100. Die grüne Fläche entspricht der Überlebens­wahrscheinlichkeit 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 $l>50$ besitzen. Dabei gibt es genau ${\tbinom {100}{l}}$ Möglichkeiten, die Zahlen eines solchen Zyklus auszuwählen (siehe Kombination ohne Wiederholung). Diese Zahlen lassen sich innerhalb des Zyklus auf $(l-1)!$ Weisen anordnen (siehe Permutation ohne Wiederholung), denn es gibt $l$ Möglichkeiten, die Startzahl des Zyklus auszuwählen. Die verbleibenden Zahlen können schließlich auf $(100-l)!$ Arten angeordnet werden. Damit ist die Anzahl der Permutationen der Zahlen von 1 bis 100 mit einem Zyklus der Länge $l>50$ gleich

${\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}$.

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

$1-{\frac {1}{100!}}\sum _{l=51}^{100}{\frac {100!}{l}}=1-\sum _{l=51}^{100}{\frac {1}{l}}=1-H_{100}+H_{50}\approx 0,31183$,

wobei $H_{n}$ die $n$-te harmonische Zahl ist. Die Wahrscheinlichkeit, dass die Gefangenen überleben, beträgt mit der Zykelfolgestrategie demnach erstaunliche 31 %.

Asymptotik

Die harmonischen Zahlen ergeben sich näherungsweise als Fläche unter der Hyperbel und lassen sich somit durch die Logarithmusfunktion approximieren

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

$1-H_{2n}+H_{n}=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2$.

Mit der Euler-Mascheroni-Konstante $\gamma$ gilt nun für $n\to \infty$

$\lim _{n\to \infty }(H_{n}-\ln n)=\gamma$,

wodurch sich eine asymptotische Überlebenswahrscheinlichkeit von

$\lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0,30685$

ergibt. Da die Folge der Wahrscheinlichkeiten zudem monoton fallend ist, überleben die Gefangenen mit der Zykelfolgestrategie in mehr als 30 % der Fälle unabhängig von der Anzahl der Gefangenen.

Optimalität

Eugene Curtin and Max Warshauer gaben 2006 einen Beweis für die Optimalität der Zykelfolgestrategie 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) Zykelschreibweise 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 Zykelfolgestrategie. Nachdem eine beliebige Strategie beim Ausgangsproblem auch in dem zweiten Problem eingesetzt werden kann, dort aber keine höhere Erfolgswahrscheinlichkeit besitzt, muss die Zykelfolgestrategie 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 Spielern 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 Zykelfolgestrategie aufmerksam. Diese Strategie zu finden, wurde in dem Konferenzbeitrag als Übungsaufgabe offengelassen. Der Beitrag wurde mit dem Best Paper Award ausgezeichnet.

Das Problem erschien im Frühjahr 2004 in der Puzzlekolummne von Joe Buhler and Elwyn Berlekamp in der Zeitschrift The Emissary des Mathematical Sciences Research Institute, wobei Kästen durch Festspeicher und farbige Zettel durch vorzeichenbehaftete Zahlen ersetzt wurden. Die Autoren stellten dabei fest, dass die Gewinnwahrscheinlichkeit auch in dem Fall, dass die Teammitglieder während der Zykelfolge ihre eigene Nummer nicht finden, erhöht werden kann. Wird in diesem Fall als Antwort das Produkt aller gefundenen Vorzeichen gegeben und ist die Länge des längsten Zyklus um eins größer als die Hälfte der (geraden) Anzahl der Spieler, dann raten die Teammitglieder, die sich in diesem Zyklus wiederfinden, entweder alle richtig oder alle falsch. Auch wenn diese Erweiterung der Strategie eine sichtbare Verbesserung bei einer kleinen Anzahl von Spielern ergibt, wird sie vernachlässigbar, wenn die Zahl der Spieler groß wird.

In der Folgezeit fand das Problem Einzug in die mathematische Fachliteratur, wo es auf unterschiedliche Weise ausgekleidet wurde, zum Beispiel mit verdeckten Karten auf einem Tisch oder Brieftaschen in Schließfächern („locker puzzle“). In der Form eines Gefangenenproblems wurde es dann 2006 von Christoph Pöppe in der Zeitschrift Spektrum der Wissenschaft und 2007 von Peter Winkler in seinem Buch Mathematical Mind-Benders gestellt. Mit leichten Abwandlungen wurde es in dieser Form unter anderem von Philippe Flajolet, Robert Sedgewick und Richard P. Stanley in ihren Lehrbüchern zur Kombinatorik übernommen.

Varianten

Leere Kästen

Gál und Miltersen betrachteten in ihrem Konferenzbeitrag zunächst den Fall, dass die Anzahl der Kästen doppelt so groß wie die Anzahl der Teammitglieder ist, wobei die Hälfte der Kästen leer ist. Dies ist ein schwierigeres Problem, da leere Kästen nirgendwohin weiterleiten und die Zykelfolgestrategie somit hier nicht eingesetzt werden kann. Es ist eine offene Frage, ob in diesem Fall die Gewinnwahrscheinlichkeit für eine wachsende Zahl von Teammitgliedern nach null strebt.

Navin Goyal und Michael Saks entwickelten 2005 basierend auf der Zykelfolgestrategie eine Strategie für Team B in einer allgemeineren Problemstellung, bei dem sowohl der Anteil leerer Kästen als auch der Anteil der Kästen, die jedes Teammitglied öffnen darf, variieren. Die Gewinnwahrscheinlichkeit strebt in diesem Fall mit wachsender Zahl von Spielern immer noch gegen null, allerdings weniger schnell als von Gál und Miltersen vermutet. Wird die Zahl der Spieler und der Anteil zu öffnender Kästen festgelassen, bleibt die Gewinnwahrscheinlichkeit echt größer als null, wenn weitere leere Kästen hinzugefügt werden.

David Avis und Anne Broadbent betrachteten 2009 eine quanteninformatische Variante, bei der Team B mit Sicherheit gewinnt.

Ziegenproblem

Adam S. Landsberg schlug 2009 folgende vereinfachte Variante des Problems vor, die sich an dem bekannten Ziegenproblem (Monty-Hall-Problem) orientiert:

Hinter drei verschlossenen Türen befinden sich zufällig verteilt ein Auto, die Autoschlüssel und eine Ziege. Es gibt zwei Spieler: der erste Spieler muss das Auto finden, der zweite Spieler die Autoschlüssel. Nur wenn beide Spieler erfolgreich sind dürfen sie mit dem Auto nach Hause fahren. Zunächst betritt der erste Spieler den Raum und darf nacheinander zwei der drei Türen öffnen. Ist er erfolgreich, werden die Türen wieder geschlossen und der zweite Spieler betritt den Raum. Der zweite Spieler darf ebenfalls zwei der drei Türen öffnen, kann allerdings in keiner Weise mit dem ersten Spieler kommunizieren. Wie groß ist die Gewinnwahrscheinlichkeit, wenn beide Spieler optimal handeln?

Wählen die beiden Spieler die Türen zufällig aus, dann beträgt die Gewinnwahrscheinlichkeit lediglich 4/9 (etwa 44 %). Die optimale Strategie lautet allerdings wie folgt:

• Spieler 1 öffnet erst Tür 1. Befindet sich das Auto darin, ist er erfolgreich. Befinden sich die Schlüssel darin, öffnet er als nächstes Tür 2, befindet sich die Ziege darin, Tür 3.
• Spieler 2 öffnet erst Tür 2. Befinden sich die Schlüssel darin, ist er erfolgreich. Befindet sich die Ziege darin, öffnet er als nächstes Tür 3, befindet sich das Auto darin, Tür 1.

Bei den sechs möglichen Verteilungen von Auto, Schlüssel und Ziege auf die drei Türen öffnen die Spieler dann die folgenden Türen (ist ein Feld grün hinterlegt, dann war der jeweilige Spieler erfolgreich):

	Auto – Schlüssel – Ziege	Auto – Ziege – Schlüssel	Schlüssel – Auto – Ziege	Schlüssel – Ziege – Auto	Ziege – Auto – Schlüssel	Ziege – Schlüssel – Auto
Spieler 1	Tür 1: Auto	Tür 1: Auto	Tür 1: Schlüssel Tür 2: Auto	Tür 1: Schlüssel Tür 2: Ziege	Tür 1: Ziege Tür 3: Schlüssel	Tür 1: Ziege Tür 3: Auto
Spieler 2	Tür 2: Schlüssel	Tür 2: Ziege Tür 3: Schlüssel	Tür 2: Auto Tür 1: Schlüssel	(Tür 2: Ziege) (Tür 3: Auto)	(Tür 2: Auto) (Tür 1: Ziege)	Tür 2: Schlüssel

Der Erfolg der Strategie besteht offenbar darin, eine Korrelation zwischen den Erfolgen beziehungsweise Misserfolgen der beiden Spieler herzustellen. Die Gewinnwahrscheinlichkeit beträgt in diesem Fall 2/3 und ist optimal, da bereits der erste Spieler keine größere Erfolgswahrscheinlichkeit besitzt. Eine weitere Variante besteht darin, drei Preise hinter den drei Türen zu verstecken und drei Spieler unabhängig voneinander jeweils einen anderen vorab bestimmten Preis mit zwei Versuchen finden zu lassen. Auch hier beträgt die Gewinnwahrscheinlichkeit bei optimaler Strategie 2/3.

Siehe auch

• Gefangenendilemma
• Gefangenenparadoxon
• Sekretärinnenproblem

Literatur

• Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009, ISBN 978-1-139-47716-1. 
• Richard P. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux, and More (= Undergraduate Texts in Mathematics). Springer, 2013, ISBN 978-1-4614-6998-8. 
• Peter Winkler: Mathematical Mind-Benders. Taylor and Francis, 2007, ISBN 978-1-56881-336-3. 

Weblinks

• 100 Gefangene – Ein stochastisches Problem, 18. April 2009
• Rob Heaton: Mathematicians hate civil liberties - 100 prisoners and 100 boxes, 13. Januar 2014 (englisch)
• Oliver Nash: Pity the prisoners, 12. Dezember 2009 (englisch)
• Jamie Mulholland: Prisoners in Boxes, Spring 2011 (PDF, englisch)