Diskussion:Problem der 100 Gefangenen

Der Artikel „Problem der 100 Gefangenen“ wurde im Juni 2014 für die Präsentation auf der Wikipedia-Hauptseite in der Rubrik „Schon gewusst?“ vorgeschlagen. Die Diskussion ist hier archiviert. So lautete der Teaser auf der damaligen Hauptseite vom 1.07.2014; die Abrufstatistik zeigt die täglichen Abrufzahlen dieses Artikels.

Grenzwert und Monotonie

Dass die Folge $(1-H_{2n}+H_{n})_{n\in \mathbb {N} }$ monoton fallend ist ergibt sich doch direkt aus

$(1-H_{2n+2}+H_{n+1})-(1-H_{2n}+H_{n})={\frac {1}{n+1}}-{\frac {1}{2n+2}}-{\frac {1}{2n+1}}<{\frac {1}{n+1}}-{\frac {1}{2n+2}}-{\frac {1}{2n+2}}=0$

Soll man das noch extra zeigen? Viele Grüße, --Quartl (Diskussion) 11:03, 13. Jun. 2014 (CEST)

Im Artikel stand:

Die Wahrscheinlichkeit, dass die Gefangenen überleben, beträgt demnach bei der Zykelfolgestrategie mehr als 30% unabhängig von der Anzahl der Gefangenen.

Das demnach ist falsch, wenn man die Monotonie nicht erwähnt. Darum ging es mir in meinem Edit. Von mir aus brauchen wir den Beweis der Monotonie nicht in den Artikel aufzunehmen, aber erwähnen sollten wir sie. --Jobu0101 (Diskussion) 11:09, 13. Jun. 2014 (CEST)

Noch eine Frage hierzu: Warum meinst du, die Existenz des Grenzwerts als solches interessiere an dieser Stelle nicht so sehr? Meiner Meinung nach ist die Existenz des Grenzwertes der Folge $(H_{n}-\ln(n))_{n\in \mathbb {N} }$ gerade das, was interessiert in diesem Zusammenhang. Dann lässt sich nämlich der Grenzwert der gesamten Folge als Summe dreier Grenzwerte schreiben, von denen sich zwei genau aufheben ($\gamma$ und $-\gamma$). Dass

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

und $\gamma$ Euler-Mascheroni-Konstante heißt, ist zwar ganz nett zu wissen (und darf auch in einem Nebensatz erwähnt werden), aber für unseren Beweis nicht weiter von Bedeutung. --Jobu0101 (Diskussion) 11:16, 13. Jun. 2014 (CEST)

Grundsätzlich gebe ich dir ja recht, aber der Artikel sollte möglichst allgemeinverständlich bleiben. Für den unbedarfteren Leser sind die Schritte einfacher nachzuvollziehen, wenn man den Grenzwert hinschreibt. Und wenn man ihn hinschreibt, dann kann man ihn auch gleich mit Namen nennen. Der wesentliche Trick besteht in der Approximation der harmonischen Zahlen durch die Logarithmusfunktion, was in dem verlinkten Artikel genauer erklärt wird. Viele Grüße, --Quartl (Diskussion) 11:40, 13. Jun. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. Quartl (Diskussion) 14:02, 19. Jun. 2014 (CEST)

Strategie

Die Strategie ist offenbar unvollständig. Was macht ein Gefangener, der entdeckt, dass der mit seiner Schublade beginnende Zyklus seine Zahl gar nicht enthält? (Er muss dazu ja nur den Zyklus ganz durchlaufen.) Offenbar muss er dann einen anderen willkürlichen Anfangspunkt außerhalb seines Zyklusses wählen (dessen Zahlen er sich tunlichst gemerkt haben sollte bzw. deren zugehörige Schubladen er bis zu seinem letzten Zug tunlichst offenlassen sollte).

Ü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.

Bei 100 „Mitspielern” besteht die Möglichkeit, dass es einen Zyklus mit 33, einen zweiten mit 33 und einen dritten mit 34 gibt. Ein Spieler, der im Zuge seiner Schubladenöffnungen zunächst zweimal an fremde Zyklen gerät, hat dann immer verloren. Solche Permutationen haben auch nur Zyklen der Länge <= 50, aber offenbar kann man mit ihnen auch mit gewisser Wahrscheinlichkeit scheitern. Die Rechnung scheint also nicht zu stimmen, weil der Fall des manchmal nötigen „Zyklensprungs” nicht berücksichtigt wurde. Man kann auch an einem kurzen Zyklus mit der eigenen Nummer scheitern, indem derselbe gar nicht oder ohne ausreichend verbliebene Öffnungslizenzen erreicht wird. (33,33,34) ist natürlich nur ein Beispiel.

--Silvicola ^Disk 00:53, 1. Jul. 2014 (CEST) Natürlich muss jeder Zyklus, der mit n beginnt, wieder in n enden. erledigtErledigt --Silvicola ^Disk 01:23, 1. Jul. 2014 (CEST)

Ein Spieler kann bei dieser Strategie nicht in einen fremden Zyklus geraten, da er auf jeden Fall mit der Schublade beginnt, die seine eigene Nummer trägt. Er kann nur verlieren, wenn sein Zyklus länger als 50% der Teilnehmerzahl ist. --Wikilaser (Diskussion) 13:07, 1. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Was passiert in der hier als optimal vorgestellten Strategie, wenn eine Schublade bereits leer ist?

Kommt das nicht vor? Bedeutet das automatisch, das das Problem nicht erfolgreich lösbar ist? (nicht signierter Beitrag von 93.129.61.138 (Diskussion) 06:47, 1. Jul 2014 (CEST))

Das kann nicht vorkommen. Jeder Gefangene findet solange neue Nummern bis er seine eigene gefunden hat (oder abbrechen muss). Um eine leere Schublade zu finden müssten zwei oder mehr Nummern auf diese Schublade verweisen, was aber laut Aufgabenstellung („Der Gefängnisleiter legt in jede Schublade die Nummer genau eines Gefangenen“) nicht zulässig ist. In der allgemeineren Problemstellung mit leeren Schubladen (siehe Abschnitt „Leere Kästen“) funktioniert die Zykelfolgestrategie dann auch nicht mehr. Grüße, --Quartl (Diskussion) 06:59, 1. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Frage zum Ablauf

Was passiert, wenn ein Gefangener seine Nummer findet? Scheidet dann diese Schulblade für die restlichen Gefangegen aus? --Wikilaser (Diskussion) 13:01, 1. Jul. 2014 (CEST)

Nein, eine einmal geöffnete Schublade wird stets wieder geschlossen und die Nummer bleibt drin. Ich vermute mal, für die Gefangenen sähe es ziemlich düster aus, wenn die gefundenen Nummern entfernt würden. Grüße, --Quartl (Diskussion) 14:19, 1. Jul. 2014 (CEST)

Der Verbleib der gefundenen Nummern in den Schubladen kommt m.E. im Artikel bisher nicht so gut raus, das erklärt vermutlich auch die vorangegangene Frage. --Michael Schumacher (Diskussion) 17:09, 2. Jul. 2014 (CEST)

An welcher Stelle wird denn angedeutet, dass die Nummern aus den Schubladen entfernt werden? Grüße, --Quartl (Diskussion) 18:26, 2. Jul. 2014 (CEST)

(wieder)finden impliziert das für mich, insbesondere da die Nummern von Aufseher erst hineingelegt werden --Michael Schumacher (Diskussion)

Ich habe nun in der Problemformulierung etwas genauer „... und muss sie danach mit ihrem Inhalt wieder schließen“ geschrieben. Ist es nun klarer? Grüße, --Quartl (Diskussion) 08:47, 3. Jul. 2014 (CEST)

Ich bin auch in diese "Vorstellungsfalle" getappt: Am Ende kontrolliert nämlich der Gefängnisleiter, (!) der ja nicht weiss, was die Gefangenen in der Schullade sehen (!), der aber mitzählt, dass jeder 50 S. aufmacht, ob jeder den Zettel mit seiner Nummer hat...

Ist der kursive Text Zitat oder "von uns". Wenn "von uns" hätte ich noch einige Vorschläge... GEEZER^{… nil nisi bene} 09:01, 3. Jul. 2014 (CEST)

Der kursive Text hat als (nicht wortgetreue) Übersetzung angefangen und wurde seitdem mehrmals umformuliert. Du kannst die Formulierungen gerne verbessern. Man kann auch fordern, dass der Gefangene nach dem Öffnen der Schubladen dem Gefängnisleiter die Nummer seiner Schublade nennen muss, wenn das klarer ist. Viele Grüße, --Quartl (Diskussion) 09:17, 3. Jul. 2014 (CEST)

• Ist:

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 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?

• Vorschlag (bitte optimieren):

Der Leiter eines Gefängnisses gibt 100 zum Tode verurteilten und durchnummerierten Gefangenen eine letzte Überlebenschance: In einem Raum befindet sich ein Schrank mit 100 geschlossenen, durchnummerierten Schubladen. In jeder Schublade befindet sich nur eine Gefangenennummer und diese Gefangenennummern in allen Schubladen sind zufallsverteilt. Der Gefängnisleiter - schweigend und mit Blick auf den Schrank - weiss, welche Gefangenennummer sich hinter welcher Schubladennummer verbirgt. Jeder Gefangene betritt nun den Raum einzeln und in der Reihenfolge seiner Gefangenennummer. Er darf 50 Schubladen öffnen, darf in diese hineinsehen und muss sie danach (mit ihrem Inhalt) wieder schließen. Danach muss er den Raum durch eine weitere Tür verlassen, bevor der nächste Gefangene in den Raum geschickt wird. Finden bei diesem Vorgang alle Gefangenen ihre eigene Nummer, werden alle begnadigt. Findet nur ein Gefangener seine Nummer nicht, müssen alle sterben. Bevor der erste Gefangene den Raum betritt, dürfen sich die Gefangenen beraten, danach ist jedoch keinerlei Kommunikation mehr möglich. Welche Strategie ist für die Gefangenen die beste?

Etwas länger, aber ich habe versucht, den Ablauf "wasserdicht" zu machen. Bitte ergänzen - damit wir hier rauskommen... GEEZER^{… nil nisi bene} 10:01, 3. Jul. 2014 (CEST)

Danke für den Vorschlag. Ich kann mir aber erst heute nachmittag genauer anschauen. Viele Grüße, --Quartl (Diskussion) 10:11, 3. Jul. 2014 (CEST)

Zunächst sollten bei einer mathematischen Problembeschreibung keine nicht weiter benötigten Dinge vorkommen. In deiner Version spielt der Gefängnisleiter keine aktive Rolle, daher könnte man ihn auch ganz wegrationalisieren (allerdings muss man dann über den Rest des Artikels nochmal drübergehen). Auch dass die Schubladen durchnummeriert sind, spielt für die Aufgabenstellung keine Rolle, weil die Schubladennummer nicht weiter vorkommt. Dass die Gefangenen den Raum durch eine andere Tür wieder verlassen müssen ist nur dann wert zu fordern, wenn dadurch der Punkt wegfallen kann, dass keine Kommunikation zwischen den Gefangenen möglich ist. Der ist aber noch drin und ist zur Unterbindung der Kommunikation etwas sicherer als nur das Verlassen des Raums. Dass die Gefangenen den Raum in irgendeiner vorgegebenen Reihenfolge betreten müssen, ist auch irrelevant, denn das Problem ist unabhängig von der Reihenfolge der Gefangenen immer das gleiche.

Vielleicht versuchen wir es andersrum: mir ist noch nicht so recht klar, welche Punkte dich an der bisherigen Aufgabenstellung stören. An der Finden-Problematik hat sich ja nichts geändert, oder ist die durch das "mit ihrem Inhalt" schon vom Tisch? Viele Grüße, --Quartl (Diskussion) 13:14, 3. Jul. 2014 (CEST)

"Auch dass die Schubladen durchnummeriert sind, spielt für die Aufgabenstellung keine Rolle" Aber Hollah ...! => "Jeder Gefangene öffnet als erstes die Schublade mit seiner eigenen Nummer." <= Woher weiss er das, wenn die Dinger nicht ... nummeriert sind? Zählt er von rechts nach links, oben nach unten oder wie? GEEZER^{… nil nisi bene} 13:26, 3. Jul. 2014 (CEST)

Für die Aufgabenstellung spielt es keine Rolle, ob die Schubladen durchnummeriert sind. Der Gefangene kann ja beispielsweise einfach auf die Schublade zeigen, in der er seine Nummer gefunden hat. Eine Nummerierung der Schubladen braucht man erst zur Beschreibung der optimalen Lösung. Viele Grüße, --Quartl (Diskussion) 13:31, 3. Jul. 2014 (CEST)

"Jeder Gefangene öffnet als erstes die Schublade mit seiner eigenen Nummer."

Ist das unzweideutig??? seine eigene Nummer - das ist die Gefangenennummer! Aber hier ist "Schubladennummer" gemeint.

Wir sollten davon ausgehen, dass nicht jeder Leser a priori weiss, was damit gemeint ist. GEEZER^{… nil nisi bene} 08:16, 4. Jul. 2014 (CEST)

Zwei Sätze davor steht doch: „Zur Beschreibung der Strategie werden nicht nur die Gefangenen, sondern auch die Schubladen von 1 bis 100 der Reihe nach durchnummeriert.“ Viele Grüße, --Quartl (Diskussion) 08:19, 4. Jul. 2014 (CEST)

Warum "verschweigt" man das dann in der "Geschichte"? Wie soll ein Gefangener "in der Geschichte" wissen, welche Schublade welche ist? Er soll ja die "mit seiner Nummer" und dann "die mit den folgenden Nummern" öffnen.

Anders wäre es, wenn er rein zufällig 50 S. aufzieht. Da spielt die Nummerierung keine Rolle. GEEZER^{… nil nisi bene} 09:21, 4. Jul. 2014 (CEST)

Du wirfst Problemstellung und Problemlösung durcheinander. Ich gebe dir ein anderes Beispiel: Angenommen, deine Aufgabe ist es, die genaue Anzahl der Schafe auf einer Weide zu ermitteln. Dein Lösungsansatz – natürlich gibt es auch andere – ist der folgende: Du nummerierst die Schafe in irgendeiner Reihenfolge mit Markierungsspray (warum haben wir dazu eigentlich noch keinen Artikel?) durch. Wenn du auf diese Weise jedes Schaf mit einer Zahl markiert hast, gibst du als Antwort die höchste Zahl. Das Durchnummerieren der Schafe ist also Teil der Lösung des Problems und nicht Teil der Aufgabenstellung. Viele Grüße, --Quartl (Diskussion) 09:33, 4. Jul. 2014 (CEST)

Ich sehe zwei Alternativen, das Dilemma zu beenden:

(a) Wir revertieren auf die zitierte Version des Urhebers des Rätsels.

(b) Wir definieren das Rätsel so, das keine Zweideutigkeiten entstehen, die dann weiter unten im Text erklärt/ausgeräumt werden müssen.

Derzeit erscheint mir Lösung (a) erstrebenswert, da (b) keinen Consensus erreicht. Ich Frage 3M an. GEEZER^{… nil nisi bene} 09:59, 4. Jul. 2014 (CEST)

Im Abschnitt "Lösung" heißt es: "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." Das bedeutet für mich, daß er sehen kann, welche Nummern die anderen aus welcher Schublade ziehen. (Was sollte es sonst heißen?) Dann beträgt sie Erfolgswahrscheinlichkeit aber 50%, weil jeder sehen kann, ob seine Nummer bei den 50 Schubladen ist, die der erste öffnen darf und dementsprechend auch öffnet. Ist sie nicht dabei, öffnet er die anderen 50, und nur beim ersten Gefangenen besteht die Gefahr des Scheiterns. (nicht signierter Beitrag von 91.47.77.33 (Diskussion) 10:15, 4. Jul 2014 (CEST))

Gemeint ist: ... die er aus den von ihm geöffneten Schubladen erhalten hat. Ich habe das ergänzt. Grüße, --Quartl (Diskussion) 10:57, 4. Jul. 2014 (CEST)

3M: Die erste kürzere Version gefällt mir als Nicht-Mathematiker besser, es steht alles wesentliche drin und man wird nicht durch Unwesentliches abgelenkt. Nur die Formulierung: "Findet nur ein Gefangener ..." sollte durch "Findet mindestens ein Gefangener ..." ersetzt werden. --UMyd (Diskussion) 12:05, 4. Jul. 2014 (CEST)

Das wurde bereits verbessert, siehe den letzten Abschnitt unten. Grüße, --Quartl (Diskussion) 12:54, 4. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Überlebenswahrscheinlichkeit 30 Prozent?

Überlebenswahrscheinlichkeit von 30 Prozent ist erstaunlich? Das ist aber weniger als 50 Prozent! Also schlechter als bei zufälliger Öffnung der Schubladen. Warum sollte jemand dann diese erstaunlich schlechte Methode wählen? Oder ist die Überlebenswahrscheinlichkeit 70 Prozent, und jemand hat sich nur verschrieben (evtl. falsch von der englischen Wikipedia kopiert)? --Agatha Bauer (Diskussion) 08:33, 2. Jul. 2014 (CEST)

Siehe den Abschnitt "Problemstellung", vorletzter Satz. Im Übrigen ist der englische Artikel von diesem hier kopiert. Grüße, --Quartl (Diskussion) 08:42, 2. Jul. 2014 (CEST)

Die Überlebenswahrscheinlichkeit beträgt nicht konstant 31%, sondern offenbar gerade bei 100 Gefangenen und 100 Schubladen. Nehmen wir die kleinstmögliche Anzahl von Gefangenen und Schubladen, beträgt die ÜW genau 50% bei 2 Gefangenen und 2 Schubladen (1 G und 1 S ergibt für mich keinen Sinn). Bei 4 Gefangenen und 4 Schubladen beträgt die ÜW nur noch ca. 41,67%. Daraus schließe ich, daß sich die ÜW mit steigender Gefangenenanzahl langsam verringert und sich vermutlich einem Grenzwert annähert. Wie errechnet man diesen Grenzwert? --Wikilaser (Diskussion) 12:24, 2. Jul. 2014 (CEST)

Bis zu welchem Abschnitt bist du denn beim Lesen des Artikels gekommen? Grüße, --Quartl (Diskussion) 12:33, 2. Jul. 2014 (CEST)

Ah, es steht ja doch da. Ich kannte den Begriff "Asymptotik" noch nicht und habe an der Stelle nicht mehr weitergelesen. Es wäre leichter verständlich, wenn man stattdessen vielleicht von der "Grenzwertbetrachtung" in der Abschnittsüberschrift sprechen würde. Allgemein wäre es auch leichter verständlich, wenn die jeweiligen Formeln nicht nur fix und fertig hingeschrieben würden, sondern auch erklärt würde, welche Rechenoperationen (und wie diese auszuführen sind) sich dahinter verbergen. Die Fakultät (z. B. 100!) kennen viele noch aus der Schule, aber zum Beispiel die 100 über dem l in Klammern oder das Summenzeichen kennt nicht jeder. Dies einmal so als Anregung, den Artikel zu verbessern. Das gilt übrigens für viele mathematische Artikel. --Wikilaser (Diskussion) 13:08, 2. Jul. 2014 (CEST)

Das Summenzeichen und die Überschrift habe ich abgeändert, aber der Ausführlichkeit des mathematischen Inhalts sind irgendwo Grenzen gesetzt. Ich habe mich sehr bemüht, den Artikel verständlich und nachvollziehbar zu schreiben, aber ein paar Grundlagen braucht man einfach. Aus diesem Grund sind durchgehend Links auf weiterführende Artikel gesetzt, die die Notation erklären und genaue Definitionen geben. Aber dass Binomialkoeffizienten nicht mehr in der Schule durchgenommen werden erschreckt mich schon etwas. Grüße, --Quartl (Diskussion) 13:59, 2. Jul. 2014 (CEST)

Ich kenne den Fall eines Schülers, dem bis zum Abitur niemals Frau Exponentialfunktion vorgestellt wurde. There's room at the bottom. --Silvicola ^Disk 15:44, 2. Jul. 2014 (CEST)

Ich hab vorhin mal aus Interesse die Wahrscheinlichkeiten geplottet. Vielleicht kann man’s ja für den Artikel brauchen, darum hab ich es gleich mal hochgeladen. -- HilberTraum (Diskussion) 13:21, 2. Jul. 2014 (CEST)

Danke, vielleicht könntest du die y-Achse noch etwas dynamischer skalieren, so ab 0.2 oder 0.25, damit sich in der Grafik mehr tut? Etwas problematisch ist natürlich, dass im Artikel an der passenden Stelle schon recht viele Bilder sind. Oder soll ich das Bild mit den harmonischen Zahlen rauswerfen? Viele Grüße, --Quartl (Diskussion) 14:02, 2. Jul. 2014 (CEST)

Die Achse ist angepasst. Ja, da ist es ein bisschen eng, hab grad auch keine gute Idee, ob man was rauswerfen sollte. Du findest sicher ein hübsches Layout :-) Grüße -- HilberTraum (Diskussion) 14:50, 2. Jul. 2014 (CEST)

Ich habe mich entschlossen, das Bild zu ersetzen. Deine Grafik habe ich noch etwas zugeschnitten und zur besseren Lesbarkeit die Schrift vergrößert. Eigentlich hätte ich gerne noch "Erfolgswahrscheinlichkeit" in "Überlebenswahrscheinlichkeit" und "n" in "Zahl der Gefangenen" abgeändert, aber ich kann leider die Texte nicht editieren, da die Fonts als Glyphen eingebunden sind. Viele Grüße, --Quartl (Diskussion) 15:13, 2. Jul. 2014 (CEST)

Hab noch eine Version mit den neuen Beschriftungen und mit einer dickeren grauen Linie hochgeladen (undgrößerer Schrift). -- HilberTraum (Diskussion) 15:33, 2. Jul. 2014 (CEST)

Die graue Linie habe ich schwarz gestrichelt, so ist sie klarer als Asymptote erkennbar. Viele Grüße, --Quartl (Diskussion) 18:29, 2. Jul. 2014 (CEST)

Im Laufe der Änderungen gestern ist die Grafik leider falsch geworden, denn es sind ja 2n Gefangene und nicht n. Ich habe also nochmal eine korrigierte Version hochgeladen. (Transparenter Hintergrund scheint mit R irgendwie nicht zu funktionieren). -- HilberTraum (Diskussion) 09:23, 3. Jul. 2014 (CEST)

Danke, der Fehler in der Skalierung ist mir gerade eben auch aufgefallen :-). Viele Grüße, --Quartl (Diskussion) 09:27, 3. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Fehlendes Adjektiv ?

• Die von dem Gefängnisleiter vorgenommene xxx Zuordnung von Gefangenen zu Schubladen...

Aus den Beispielen ist ja ersichtlich, dass ein sadistischer, aber mathematisch begabter Gefängnisleiter (ich hatte so einen in der Sexta und Quinta) garantieren könnte, dass sie es nicht schaffen (Sie tanzen ja der Reihe nach (1, 2 ... 99, 100) an). Sollte man da nicht ein zwingendes "zufällige" oder so hinzufügen? GEEZER^{… nil nisi bene} 15:05, 2. Jul. 2014 (CEST)

Gut erkannt. Wenn der Gefängnisleiter die Zuordnung nicht zufällig vornimmt (was er nach Aufgabenstellung eigentlich müsste), muss er nur sicherstellen, dass die Verteilung der Zahlen auf die Schubladen einen Zyklus mit einer Länge größer als 50 bildet, dann haben die Gefangenen keine Chance. Die beiden Beispiele sind natürlich konstruiert und können daher nicht wirklich zufällig sein. Viele Grüße, --Quartl (Diskussion) 15:21, 2. Jul. 2014 (CEST)

Man könnte ihn erblinden lassen ... (blind justice) Drama, Baby, Drama! ;-)) GEEZER^{… nil nisi bene} 15:24, 2. Jul. 2014 (CEST)

Wohl eher blinder Sadismus. Mit dem Aufmacher wäre jedes Stochastikbuch ein garantierter Bestseller. Aber wir schweifen ab ;-). Viele Grüße, --Quartl (Diskussion) 17:10, 2. Jul. 2014 (CEST)

• Um es für den Gefängnisleiter unmöglich zu machen, absichtlich eine Permutation mit einem Zyklus länger als 50 zu verwenden (er liest bestimmt auch Wikipedia ;-) und hält sich dann bestimmt nicht an die Anweisung, die Nummern in zufälliger Reihenfolge abzulegen!), sollten die __Namen__ der Gefangenen in die Schubladen. Die Nummerierung (Zuodnung von Namen zu Nummern) könnten dann die Gefangenen in ihrer Beratung vornehmen ("Schmitz ist Nr. 1, Müller ist Nr. 2, Schröder ist Nr. 3, ..."). Aber selbst wenn die Gefangenen bereits vorab Nummern haben und diese in die Schubladen gelegt werden, können (und sollten!) die Gefangenen in ihrer Beratung eine andere Nummerierung verabreden, um einen böswilligen Gefängnisleiter auszutricksen ("Gefangener 35 ist Nr. 1, Gefangener 23 ist Nr. 2, Gefangener 1 ist Nr. 3, ..."). Da also die Nummerierung nur essentiell für die Lösung ist, nicht für die Problemstellung, würde ich vorschlagen, die Formulierung des Problems entsprechend anzupassen (Vanda (Diskussion) 11:10, 28. Dez. 2014 (CET)):

Der Leiter eines Gefängnisses gibt 100 zum Tode verurteilten Gefangenen (mit eindeutigen Namen) eine letzte Chance. In einem Raum befindet sich ein Schrank mit 100 Schubladen. Der Gefängnisleiter legt in jede Schublade einen Zettel mit dem Namen 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 ihren eigenen Namen in einer der Schubladen, werden die Gefangenen begnadigt. Findet irgendein Gefangener seinen Namen nicht, müssen alle Gefangenen sterben. Bevor der erste Gefangene den Raum betritt, dürfen sich die Gefangenen den Raum mit dem Schrank und den verschlossenen Schubladen ansehen und sich dann miteinander beraten. Danach ist jedoch keinerlei Kommunikation mehr möglich. Was ist für die Gefangenen die beste Strategie?

Hallo Vanda, grundsätzlich müssen wir uns in der Wikipedia schon an die Vorgaben aus der Literatur halten, alles andere wäre nämlich Theoriefindung. An sich ist es aber egal, ob die Namen (sofern diese eindeutig sind) oder Nummern der Gefangenen auf den Zetteln stehen. Die Nummern haben, sofern auch die Schubladen durchnummeriert werden, den Vorteil, dass die folgenden Erklärungen mit Hilfe von Permutationen leichter verständlich werden. Die Zufälligkeit der dem Problem zugrunde liegenden Permutation spielt mathematisch eine entscheidende Rolle. In der Literatur sorgt stets der Gefängnisleiter für den Zufall und ist daran laut Aufgabenstellung auch gebunden. Der Zufall ist damit Teil der Problemstellung. Natürlich könnten auch die Gefangenen eine zufällige Nummerierung der Schubladen vornehmen. Der Zufall wäre dann Teil der Lösung (vgl. randomisierter Algorithmus). Das Szenario des „böswilligen Gefängnisleiters“ wird im Buch von Sedgewick/Flajolet im Rahmen einer Übungsaufgabe (S. 177) sogar kurz diskutiert. Allerdings rechtfertigt das nicht eine Änderung der Aufgabenstellung, sondern höchstens eine Erwähnung irgendwo im Text. Grüße, --Quartl (Diskussion) 13:33, 28. Dez. 2014 (CET)

PS: Ich habe nun den böswilligen Gefängnisleiter als Variante im Artikel ergänzt. --Quartl (Diskussion) 17:01, 28. Dez. 2014 (CET)

Danke, die Situation mit einem böswilligen Gefängnisleiter als eine Variante zu beschreiben ist eine gute Idee! Vanda (Diskussion) 19:53, 1. Jan. 2015 (CET)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Strategie - noch nicht gesehene Nummer

Im Abschnitt "Strategie" steht:

"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."

Was ist da mit "noch nicht gesehene Nummer" gemeint? Eine, die er noch nicht gesehen hat, oder die noch keiner gesehen hat? "Noch keiner" kann ja nicht sein, siehe das Beispiel, also muss "die er noch nicht gesehen hat" gemeint sein. Der Algorithmus gibt das aber nicht her, da das Abbruchkriterium bei 4. die 50. Schublade ist, wenn er seine Nummer nicht findet. Wenn der Gefangene mit der Nummer 33 also Schublade 33 aufmacht und da liegt die 14 drin, in der 14 liegt die 28 und in der 28 die 14, dann macht er lt. Algorithmus die Schubladen 14 und 28 mehrfach (49-mal) auf und findet sehr wohl Zahlen, die er schon gesehen hat.

Es ist aber ja trivial zu ergänzen und eigentlich selbstverständlich, dass jeder Gefangene 50 verschiedene Schubladen aufmacht. Wozu also der Hinweis, dass er eine noch nicht gesehen Zahl vorfindet?

Habe den missverständlichen und nutzlosen Hinweis auf die "noch nicht gesehene Nummer" ersetzt. --Ulrich Matthias (Diskussion) 21:17, 3. Jan. 2020 (CET)

Es gibt nur zwei grundlegende Möglichkeiten (mit entsprechend vielen Varianten), die dazu führen, daß jeder Gefangene 50 verschiedene Schubladen öffnet, nämlich dann, wenn die Nummernverteilung zwei 50er Zyklen oder einen 100er Zyklus verursacht. --Wikilaser (Diskussion) 01:41, 4. Jul. 2014 (CEST)

Und was soll im Beispiel der Hinweis am Ende von "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 dies dem zweiten Gefangenen bekannt war? Von dem Wissen hat doch keiner der Gefangenen etwas? Wozu also der Hinweis?

Dem zweiten Gefangenen kann das nur bekannt sein, wenn er denselben Zyklus durchläuft wie der erste Gefangene. Das Wissen um den Zyklus des ersten Gefangenen nützt ihm jedoch nichts, da hast Du Recht. --Wikilaser (Diskussion) 01:41, 4. Jul. 2014 (CEST)

--AchimP (Diskussion) 17:06, 2. Jul. 2014 (CEST)

In deinem Beispiel liegt die 14 zweimal drin, das ist so nicht vorgesehen. --Michael Schumacher (Diskussion) 17:13, 2. Jul. 2014 (CEST)

Da hast Du völlig recht. Sorry. --AchimP (Diskussion) 17:31, 2. Jul. 2014 (CEST)

Den Nachsatz habe ich umformuliert. Grüße, --Quartl (Diskussion) 18:26, 2. Jul. 2014 (CEST)

Danke. --AchimP (Diskussion) 18:48, 2. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

„Findet nur ein Gefangener seine Nummer nicht...“

Das liest sich für mich immer so, als wäre der Fall “genau einer” damit gemeint - finden also zwei ihre Nummer nicht, passiert nichts/etwas anderes. --Michael Schumacher (Diskussion) 12:42, 3. Jul. 2014 (CEST)

Gemeint ist natürlich mindestens einer, wobei man auch bereits nach dem ersten Unglücksraben Schluss machen kann. Ich habe den Punkt umformuliert. Grüße, --Quartl (Diskussion) 13:17, 3. Jul. 2014 (CEST)

Dieser Abschnitt kann archiviert werden. --Quartl (Diskussion) 12:15, 2. Jan. 2015 (CET)

Lösung vermischt zwei Ebenen

Hallo; bei der Lösung werden zwei Ebenen unzulässig vermischt: zum einen die Erzählebene, in der die Gefangenen mit dem Problem konfrontiert sind und zum anderen die Metaebene des Lesers bzw. Problemlösers. Die Lösung beruht auf einer expliziten Nummerierung der Schubladen, welche sich der Leser zwar vorstellen kann, die aber den Gefangenen nicht zur Verfügung steht (zumindest wird eine solche Nummerierung in der Aufgabenstellung nicht erwähnt). Es sei denn, man unterstellt dem Leser die Macht, den Gefangenen gottgleich die zur Lösung nötigen Nummern auf den Schubladen auf wundersame Weise im rechten Moment erscheinen zu lassen. Letztendlich soll ja das Problem der Gefangenen (in der Erzählebene) gelöst werden... --Geodel (Diskussion) 19:23, 6. Okt. 2014 (CEST)

Das scheint mir auch ein Problem zu sein. Wenn die Gefangenen verschiedene Nummerierungen zugrundelegen, bricht das alles zusammen. Man könnte die Rahmenerzählung so abändern, dass eine natürliche Ordnung evident ist: ohnehin schon von 1 bis 100 nummerierte Schubladen; Schubladen wie bei einem alten Apothekenschrank in zeilenweise von links nach rechts abzuzählender 10×10-Anordnung, auf die man sich vorab verständigen könnte; vornummerierte Türen an einem langen linearen Behördenflur usw. --Silvicola ^Disk 19:37, 6. Okt. 2014 (CEST)

Ich weiß nicht, ob man die Rahmenerzählung einfach abändern darf, wenn sie genauso in der Literatur zu finden ist. Stattdessen müsste man entweder den Lösungsweg anpassen oder aber im Artikel vermerken, dass die Lösungsstrategie in dieser Form eigentlich nicht anwendbar ist. --Geodel (Diskussion) 09:53, 7. Okt. 2014 (CEST)

Heiklen Punkt angesprochen. Könnte wohl noch besser formuliert werden. --Silvicola ^Disk 15:46, 7. Okt. 2014 (CEST)

Besser so? Grüße, --Quartl (Diskussion) 15:56, 7. Okt. 2014 (CEST)

Deine Lösung berücksichtigt die „lebensweltlichen“ Einwände nicht, die jetzt vielleicht bald kommen:

• „Ja, dürfen denn gerade Gefangene einfach so herumschmieren auf fremden Schubladen?“
• „Was ist, wenn sie nichts zu schreiben haben?“
• „Was ist, wenn sie nichts zu schreiben haben?“
• „Was aber, wenn ein Wärter, nachdem der beschriftende erste Gefangene wieder hinausgegangen ist, wieder alles abwischt? – Man kann das Schubladenzimmer doch nicht unkontrolliert lassen, sonst könnten die Gefangenen ja heimlich alle hundert Schubladen öffnen, bis auf den letzten.“
• „Jede Beschriftung durch Gefangene kann ein (steganographischer) versteckter Kanal sein.“
• „Unter hundert Gefangenen gibt's bestimmt einen Analphabeten!“ (Dieser Einwand trifft sicher auch andere Lösungsversuche.)

usw. usf. --Silvicola ^Disk 16:50, 7. Okt. 2014 (CEST)

Ok, ich habe das fehlende „gedanklich“ ergänzt. Wir gehen einfach davon aus, dass die Gefangenen alle bis 100 zählen können. Grüße, --Quartl (Diskussion) 16:58, 7. Okt. 2014 (CEST)

Eine kühne Annahme, wenn ich so an meine jüngeren Erfahrungen an der Supermarktkasse denke.

Hoffentlich ist wenigstens kein Politiker unter den Gefangenen. Denn Du weißt doch wohl, wie die zählen? — 1, 10, 100, 1.000, 10.000, 100.000, 1.000.000 … Manche auch im moderneren und einfacheren sogenannten amerikanischen Fünf-Ionen-System: 1.000.000, 1.000.000.000, 1.000.000.000.000, 1.000.000.000.000.000, need a fall guy. Wozu hat man schließlich gerade fünf Finger an der freien Hand?

--Silvicola ^Disk 18:27, 7. Okt. 2014 (CEST)

In der Aufgabenstellung heißt es:"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." Es wird mit keinem Wort erwähnt, dass alle 100 Gefangenen das Innere des Raumes und die Geometrie des Schranks bzw. die Anordnung der Schubladen vor ihrem Betreten bereits kennen. Wie können sie dann vorher schon "die Schubladen gedanklich mit den Zahlen von 1 bis 100 durchnummerieren"? --Geodel (Diskussion) 17:45, 10. Okt. 2014 (CEST)

Letztendlich steckt das in dem Satz Bevor der erste Gefangene den Raum betritt, dürfen sich die Gefangenen beraten drin. Wären nämlich die Gefangenen nicht über das ganze Setup vorab informiert worden, gäbe es nichts zu beraten. Vielleicht hast du aber einen Vorschlag für eine bessere Formulierung? Grüße, --Quartl (Diskussion) 18:57, 10. Okt. 2014 (CEST)

Zwei Sätze, die ich nicht verstehe

Eine weitere wichtige Beobachtung ist, dass dabei der Erfolg eines Gefangenen nicht unabhängig vom Erfolg der anderen Gefangenen ist.

Was spielt denn das für meinen Erfolg beim Nummersuchen für eine Rolle, ob der vorherige Gefangene die richtige Schublade geöffnet hat?! Wenn ich die richtige Schublade öffne und danach der nächste Gefangene dran ist, dann hat der doch keine höhere Chance, bloß weil ich die richtige Schublade gefunden habe. Oder ist damit einfach nur gemeint, dass es eine kleine Wahrscheinlichkeit gibt, dass der nächste Gefangene sich in dem selben Permutationszyklus wie ich befindet, und er damit automatisch auch „gewinnt“, wenn ich gewonnen habe?

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.

Wenn man 100 Schubladen vor sich hat und in allen 100 Schubladen sind verschiedene Nummern, dann ist es unmöglich, zwei identische Nummern vorzufinden. Wie soll man diesen Satz bitte verstehen? Wenn ich 50 Schubladen öffne (völlig egal ob mithilfe der Permutation oder zufällig), dann habe ich entweder einmal meine eigene Nummer und 49 Nummern anderer Gefangener oder ich habe 50 Nummern anderer Gefangener. Aber ich habe nirgendwo eine Nummer, die ich in einer anderen Schublade schon gesehen habe! Also, entweder ich verstehe diesen Satz einfach falsch, dann ist er schlecht formuliert … oder der Satz ergibt keinen Sinn.--31.17.159.244 04:35, 13. Okt. 2015 (CEST)

Zum ersten Satz: Die Zykelfolgestrategie ändert nichts an der Erfolgswahrscheinlichkeit für einen einzelnen Gefangenen, wohl aber an der Erfolgswahrscheinlichkeit für alle Gefangenen. Wenn der erste Gefangene mit der Zykelfolgestrategie erfolgreich war, dann hat der zweite Gefangene mit dieser Strategie tatsächlich eine höhere Erfolgswahrscheinlichkeit. Das kann man gut am Beispiel von vier Gefangenen sehen, die jeweils zwei Schubladen öffnen dürfen: wenn der erste Gefangene mit der Zykelfolgestrategie erfolgreich ist, dann werden es auch die anderen drei sein.

Zum zweiten Satz: Nicht jede Strategie stellt sicher, dass ein Gefangener stets als nächstes eine noch nicht geöffnete Schublade öffnen wird. Zum Beispiel ist das nicht der Fall, wenn die Schubladen nach dem Öffnen direkt wieder verschlossen würden und zur Auswahl der nächsten Schublade einfach ein 100-seitiger Würfel geworfen wird. Das ist nur der Fall, wenn Gefangenen ein injektive Abbildung verwenden, um die Nummer der nächsten Schublade zu finden. Diese Injektivität muss bei einer gegebenen Strategie erstmal nachgewiesen werden.

Viele Grüße, --Quartl (Diskussion) 09:03, 13. Okt. 2015 (CEST)