Python Tutorial deutsch, Das 100 Gefangene Problem

Hier simulieren wir unterschiedliche Strategien beim 100 Gefangenen Problem.

[olavhumbek]

Ein gutes Video zum Problem der 100 Gefangenen gibt es von Mathegym. Die Mathematik dahinter gut erklärt. Titel des Videos hier auf YouTube ist: Problem der 100 Gefangenen. Er hatte eine Überlebenswahrscheinlichkeit von ca. 31% ausgerechnet.

[MarcoKohlmann]

Nach den ersten 10 Minuten dieses Youtube Videos hatte ich es verstanden.

Kanal: Weitz / HAW Hamburg
Video: Das Problem der 100 Gefangenen oder: Eine unmögliche Wette (?)

[jensgutow]

Erstmal Danke für das Video! Ist immer wieder gut!

Im Wikipedia-Link ist die Erklärung mit angegeben.

Hier mal eine Art Zusammenfassung.

Jede Permuatation kann auch durch seine Zyklendarstellung beschrieben werden. Wenn man sich anschaut, wohin das 1. Element "wandert" (z.B. an die Stelle 3), dann schaut man sich an, was mit den 3. passiert usw.. Das Ergebnis ist dann z.B das man einen Zyklus 3, 4, 2 bekommt (das 2. Element kommt dann wieder an die 1. Stelle -> daher dann auch der Name Zyklus).
Jede Permutation besteht dann aus einer bestimmten Anzahl von Zyklen. Jeder Zyklus hat eine bestimmte Länge (die Anzahl der Elemente im Zyklus).
Nicht veränderte Elemente sind "entartete" Zyklen und besitzen die Länge 1.
Wenn eine Permutation N mal wiederholt wird, (und es gibt einen Zyklus mit der Länge N), dann ist das Resultat, das alle Elemente des Zyklusses sich wieder an ihrer Orginalstelle sich befinden.

Jeder Gefangene befindet sich genau in einem (seinem) Zyklus. Den Einstieg in diesem Zyklus findet man, indem das Fach mit der Nummer des Gefangenen geöffnet wird. Und nun muss man sich "entlanghangeln", um seine eigene Nummer zu finden. Wenn die Zykluslänge <=50 ist, dann wird nach spätestens 50 Versuchen die eigene Nummer gefunden.
Im anderen Fall (Zykluslänge > 50) kommt es auf dem "Einstiegspunkt" im Zyklus an.

Bei unserem Problem geht es nun darum, die Wahrscheinlichkeit einer Permutation mit einer Zyklenlänge von > 50 zu finden (also Zyklen mit der Länge 51..100).
Bei jedem Zyklus mit der Länge L > 50 gibt es dann L-50 Gefangene, die mit der "Zyklusstrategie" NICHT erfogreich sind.

Eine Permutation mit 100 Elementen kann höchstens einen Zyklus mit einer Zykluslänge von > 50 besitzen.

Nun muss man "nur" noch die "guten" und die "schlechten" Permutationen zählen.

[lutzrichter]

Erst mal vielen Dank für die tollen Python- Videos. Zu dem mathematischen Problem: Die Annahme, daß die Chance ohne Strategie 0, 5 ist, kann nach meiner Ansicht stimmen. Wenn das erste Fach geöffnet wird, bleiben nur noch 99, dann 98 etc. (Voraussetzung, die Fächer werden pro Gefangenem nur einmal geöffnet). Damit steigt die Chance seinen Zettel zu finden, mit jedem geöffneten Fach. Somit ist die Chance für jeden einzelnen Gefangenen viel höher als 50% (weiß nicht, wie man das ausrechnet, überschlägig vielleicht 70%). Bei der Lösung mit der Strategie kann es auch vorkommen, daß der Gefangene in einer Schleife "gefangen" ist, und seine Nummer nicht in dem Kreis liegt. Das ird bei der Betrachtung irgendwie nicht berücksichtigt.

[vladimirsch.]

Hallo Gravitar,

ich würde im Namen einiger sprechen und zu aller erst danken für den Content den Du kreierst.
Als zweites wollte ich Dich fragen, ob Du deine PySide Serie noch fortsetzen wirst. Ich muss gestehen, dass Deine didaktische Art mir mehr zusagt, als alles andere was ich zu dem Thema auf youtube in engl. gefunden habe.

Beste Grüße

[brotherlui]

In der Schublade 63 ist die 18, in der 18 ist die 89, in der 89 ist die 22, etc etc. Hast dich beim suchen der 63 verzählt. ;-)

[markoschonwandt]

Die Wahrscheinlichkeit ist so hoch, weil die Zahlenkreise immer die Selben sind. wenn z.B der erste Gefangene 30 Schubladen öffnen muss um seine Zahl zu bekommen, dann weiß man das die anderen 29 Gefangen mit den Nummer im Zahlenkreis des ersten Gafangen es auch in unter 50 Versuchen schaffen. Fehlen nur noch die anderen 70 Gefangenen bei denn man hoöffen muss das die Zahlenkreise nicht länger als 50 sind.

[romanbuchta]

Könnte mir nur vorstellen das - da jeder mit einer einzigartigen Zahl (Kästchen) beginnt - die Zahl der unnötig geöffneten Kästchen sich reduziert. Frage mich aber gerade, wie hoch die Wahrscheinlichkeit ist, wenn alle 100 immer nur stets die ersten 50 Kästchen öffnen würden. Dann sollte es doch mehr als die 31% (kopfkratz....)