Ein kleines Rätsel

[mfb]

Sarf: Du bist mit der Wahrscheinlichkeit auf dem Holzweg. Als Grenzwert für beliebig viele Häftlinge erhält man 1-ln(2), also grob 30%.

Für einen Zyklus mit Länge r gibt es (100 über r) mögliche beteiligte Häftlinge. Innerhalb des Zyklus gibt es (r-1)!=r!/r mögliche Anordnungen, außerhalb des Zyklus (100-r)! mögliche.

(100 über r) = 100! / (r!*(100-r)!)

Ergibt damit Möglichkeiten:
Sum[r=51...100]( 100! / (r!*(100-r)!) * r!/r * (100-r)! )
Gekürzt und konstante 100! rausgezogen:
100! * Sum[r=51...100](1/r)
100! ist aber gerade die Zahl der insgesamt möglichen Permutationen, damit erhält man als "Risiko"
Sum[r=51...100](1/r) =~ ln(2)
Oder eben als Wahrscheinlichkeit, dass die Häftlinge freikommen
1-ln(2) =~ 30%

 

[Sarf]

genau so nen "trick" habe ich gesucht
habe es nicht hinbekommen, es so schön direkt zu berechnen, nachts um zwei ist auch nicht so der produktive moment...


mfg

 

[Termi_RoD]

€: Och verdammt, ich sollte mein Kopf nach durchzechter Nacht nicht vorm ersten Kaffee mit Kodierungstheorie martern... also vergesst, was ich grad geschrieben hab, habs ja schon eingesehen...


Hi Leuts,

die Lösung ist ja vom Ansatz her schön und gut, aber IMHO trotzdem nicht richtig. Da die Zuweisung der Zahlen zu den Gefangenen willkürlich geschieht, hat doch immernoch jeder eine Chance von >=50%, dass sein Name in Wirklichkeit in einem anderen Zyklus steckt?

Die 30% geben doch nur die Wahrscheinlichkeit dafür an, dass kein Zyklus > 50 besteht?

Sind es 2 Zyklen mit 50, so ist jeder mit 50% Wahrscheinlichkeit im richtigen Zyklus.
Nun ist ja aber genau Länge <=50 gewünscht, was die Wahrscheinlichkeit, im falschen Zyklus zu sitzen noch vergrößert, also >50%?

Am Ende kommen wir auf eine Wahrscheinlichkeit von < 2^-100, da nach dem Algorithmus viele ihre 50 Versuche garnicht sinnvoll nutzen, sondern Kisten doppelt aufdecken.

Grüße Termi

 

[mfb]

Falsch

Da jeder Häftling mit "seiner" Kiste beginnt, ist er zwingend im richtigen Zyklus.
Das klingt auf den ersten Blick vielleicht etwas verwirrend, funktioniert aber. Der richtige Zyklus für den Häftling beinhaltet ja unter anderem "seine" Kiste.

Es ist richtig, dass jeder Häftling nur 50% Chance hat, seinen Namen zu finden. Aber die Wahrscheinlichkeiten sind eben in extremem Maße voneinander abhängig.

Spoiler

Lösung:
Die Gefangenen nummerieren sich irgendwie durch, sodass jeder eine Zahl von eins bis einhundert erhält.
Gefangener a öffnet dann zunächst Kiste a. Findet er seinen Namen, ist er fertig. Findet er den Namen (bzw. die Nummer) b, dann öffnet er Kiste b und so weiter, bis er eben seinen Namen findet.

Damit erhalten die Häftlinge jeden Tag eine Freilassungschance von ca. 31%. Vorausgesetzt, es können sich alle alle 100 Zuordnungen von Namen und Zahlen merken.


Wieso das funktioniert:
Mit dieser Strategie bildet man "Ketten" von Gefangenen. Ein Beispiel mit 8 Gefangenen:

1 2 3 4 5 6 7 8 <- Kistennummer
3 1 8 6 5 7 4 2 <- "Name" in der Kiste

Gefangener 1 öffnet also Kiste 1 -> Kiste 3 -> Kiste 8 -> Kiste 2 und ist fertig
Gefangener 3 geht die gleiche Kette durch: Kiste 3 -> Kiste 8 -> Kiste 2 -> Kiste 1 und ist fertig
Analog finden auch Nummer 8 und Nummer 2 damit ihre Kiste.

4,6 und 7 bilden ebenfalls eine solche Kette und finden alle ihre Kiste.
5 ist eine eigene Kette und findet seine Kiste.

Das System versagt genau dann, wenn eine solche Kette länger als die Hälfte der Gefangenen ist. Andernfalls finden alle Gefangenen ihre Kiste, sie laufen genau einmal ihre Kette ab.


Die Freilassungschance
Gesucht ist also die Chance, dass keine Kette länger als 50 Kisten ist. Dazu wird zunächst die Wahrscheinlichkeit berechnet, dass es eine solche längere Kette gibt: Da 2*51>100, kann es maximal eine solche geben und was mit den anderen Nummern passiert, ist egal.
Vorsicht, wird mathematischer: Für eine Kette der Länge r gibt es (100 über r) = 100! / (r!*(100-r)!) mögliche beteiligte Häftlinge. Innerhalb der Kette gibt es (r-1)!=r!/r mögliche Reihenfolgen, außerhalb davon (100-r)! mögliche.


Insgesamt gibt es also an ungünstigen Möglichkeiten:
Sum[r=51...100] ( 100! / (r!*(100-r)!) * r!/r * (100-r)! )
Gekürzt und konstante 100! rausgezogen:
= 100! * Sum[r=51...100](1/r)
100! ist aber gerade die Zahl der gesamten Möglichkeiten, damit erhält man als "Risiko"
Sum[r=51...100](1/r) =~ ln(2)
Oder eben als Wahrscheinlichkeit, dass die Häftlinge freikommen:
1-ln(2) =~ 30%

Rechnet man die Summe selbst aus, ergibt sich ~31,183% Freilassungschance.

Die obige Herleitung funktioniert allgemein für n Häftlinge, die n/2 Kisten öffnen dürfen (n gerade). Für große Häftlinge wird die Näherung der Summe beliebig genau, die Wahrscheinlichkeit nähert sich also von oben an 1-ln(2) an.