Der Gefängnisdirektor hat Langeweile

[Musagetes]

Hi Otmar,

da ich auch durch herunter brechen der Anzahl der Gefangenen und durch Probieren auf die Suchstrategie gekommen war.
(Mir fehlte nur noch die konkrete Aufgabe des Pfarrers.)

Dabei fiel mir auf, …….

Mehr ->

dass ein wesendlicher Erfolg dieser Suchstrategie darauf beruht, dass bei der Abfrage der einzelnen Fächer durch die Gefangen in Ihren Zyklen einer geschlossenen Fächer-Ausweis-Kette, durch die Prozedur, eines gefundenen Ausweises eines Gefangen, dessen zugeordnetes Fach als nächstes geöffnet wird.
Dadurch wird im Vorhinein ausgeschlossen, dass bei der Suche eines Gefangenen nach seinem Ausweis in einem Zyklus, in einem, einen Gefangenen zugeordneten Fach, dessen eigener Ausweis gefunden werden kann, da er von dessen Ausweis erst auf das Fach verwiesen wurde.

Durch diese Optimierung, der Suchstrategie wird erst diese hohe ….

@Otmar:...
…….. Wahrscheinlichkeit, die größer als 1-ln(2) ist, ……….

…. erreicht.

Ich hoffe, Ihr konntet meinen Anmerkungen folgen?!

Gruß
Musagetes

[Otmar]

Hallo Musagetes,
jetzt tut es mir wirklich leid, dass ich relativ früh so viele Tipps gegeben hatte.
Da hat mich mein Gefühl, dass Tipps nötig wären, sehr getäuscht.
Totat schade, denn ich glaube nicht, dass ich eine vergleichbare Aufgabe habe, bei der ich es anders machen könnte.
Gruß Otmar

[Kolabord]

Ich finde nicht, dass du zu viele Tipps gegeben hast. Eigentlich habe ich nur den einen letzten Tipp benötigt und du hast die Tipps auch immer in Spoiler gesetzt. Wenn ich sie also nicht lesen möchte kann ich es auch lassen und so an dem Rätsel rätseln.

[black]

@Otmar:

Ein klasse Rätsel hast du uns da raus gesucht.

Die Lösung ist so einleuchtend und elegant, dass sich im Nachhinein folgende Smileys aufdrängen:

[Zentimeter]

Mir haben die Tipps auch geholfen, das Rätsel nachträglich nachzuvollziehen!
So war der Weg zum Ziel nicht ganz so steil!
Wobei ich gestehen muss, dass mir das System - trotz Erklärung - erst dann wirklich klar wurde, als ich mir das Ganze mal aufgemalt und durchgespielt hatte!

Danke für ein tolles und für mich völlig neuartiges Rätsel!

[Otmar]

Freut mich, dass das Rätsel auch nach so langer Zeit noch gefunden und gelöst wird.

[Zentimeter]

Mein Problem ist, dass ich es zwar nachvollziehen kann, wenn es einem so schön häppchenweise serviert wird, aber selbst nicht darauf gekommen wäre.

Zum Beispiel frage ich mich, wenn ich jetzt in diese Situation käme (sowas kann ja schließlich jederzeit passieren ) aber keinen Pfarrer hätte.
Ich weiss zwar meine Gefangenennummer, habe aber keinen Kontakt mit den anderen Insassen.

Der gelangweilte Gefängnisdirektor schlägt mir, ganz alleine, unabhängig von den anderren Gefangene vor, ich dürfe 25 Türen des Schranks öffnen, falls ich meinen Ausweis fände, wäre ich frei.

Könnte ich dann mit dieser Methode die Wahrscheinlichkeit, freizukommen steigern, so dass sie günstiger als 50/50 steht, vorrausgesetzt, die Fächer wurden zufällig befüllt?

Ich weiss es nicht!

[Otmar]

@Zentimeter

Mein Problem ist, dass ich es zwar nachvollziehen kann, wenn es einem so schön häppchenweise serviert wird, aber selbst nicht darauf gekommen wäre.

Da hast du Recht. Am schönsten ist es, wenn man selbst draufkommt und keine Hilfe braucht. Das wäre bei diesem Rätsel sogar möglich gewesen, aber es ist natürlich auch ein sehr schweres Rätsel.

Ich hab es deshalb gestellt, weil ich das Ergebnis so verblüffend fand. Man möchte ja erstmal meinen, das kann gar nicht gehen, und dann gibt es doch eine nachvollziehbare Möglichkeit zur Lösung.

Zum Beispiel frage ich mich, wenn ich jetzt in diese Situation käme (sowas kann ja schließlich jederzeit passieren) aber keinen Pfarrer hätte.
Ich weiss zwar meine Gefangenennummer, habe aber keinen Kontakt mit den anderen Insassen.

Der gelangweilte Gefängnisdirektor schlägt mir, ganz alleine, unabhängig von den anderen Gefangene vor, ich dürfe 25 Türen des Schranks öffnen, falls ich meinen Ausweis fände, wäre ich frei.

Könnte ich dann mit dieser Methode die Wahrscheinlichkeit, freizukommen steigern, so dass sie günstiger als 50/50 steht, vorausgesetzt, die Fächer wurden zufällig befüllt?

Mehr ->

Dazu hatte ich schon was geschrieben. Hier ein kleiner Auszug aus der Diskussion:

Ohne Hilfe des Pfarrers könnten die Gefangenen mit etwas Glück auch freikommen. Denn dann beträgt die Wahrscheinlichkeit, das alle die Fächer öffnen, hinter denen die Ausweise liegen immerhin noch 31,675389... Prozent

Die beträgt doch bei den ersten beiden Probanden ohne Pfarrer/Info kaum über 25%.
Und dann kommen noch 48 weiter, die die Gesamtchance noch mehr verringern.

für den ersten Gefangenen sind es 50%. Wenn man die Gefangenen einzeln betrachtet sind es für jeden Gefangenen für sich genommen auch 50%. Da kann man die Statistik nicht überlisten. Die Aufgabe der Gefangenen ist es deshalb, eine Suchstrategie zu entwickeln, bei der die Ereignisse, den Ausweis finden oder den Ausweis nicht finden, für verschiedene Gefangene in hohem Maße voneinander abhängen. Jedenfalls viel viel stärker, als dass ein Multiplizieren von Einzelwahrscheinlichkeiten zum Berechnen der Wahrscheinlichkeit für das kombinierte Ereignis auch nur in Annäherung richtig wäre. Das Interessante ist, dass es so eine Suchstrategie (die gar nicht so schwer zu finden ist) gibt. Also eine Strategie, bei der, wenn ein Gefangener versagt, ein anderer auch mit hoher Wahrscheinlichkeit versagt und umgekehrt.
Wenn du die Strategie hast, ist es nur noch ein kleiner Schritt, die Aufgabe des Pfarrers festzulegen.
Mit Wahrscheinlichkeiten musst du dich dabei nicht abplagen. Und es gibt auch sonst nicht so viel zum Rechnen. Dafür hab ich den Pfarrer zugefügt, der das sichere Ereignis der Freilassung erzwingen kann und damit aus dem rein mathematischen Problem ein Rätsel wird.

Wenn du allein bist, brauchst du keinen Kontakt zu den anderen. Du kannst irgendeine Nummerierung wählen. Da die anderen nicht mitspielen, ist das ganz egal. Die Wahrscheinlichkeit, dass du raus kommst ist 50%. Die Rechnung dazu hatte ich natürlich nicht geben können, weil ich das Rätsel sonst aufgelöst hätte.

Aber so schwer ist das nicht:

Bei n = 50 Gefangenen gibt es M = n! Möglichkeiten, wie der Schrank bezüglich der von die gewählten Nummerierung eingeräumt sein könnte, jede ist gleichwahrscheinlich. Du bleibst im Gefängnis, wenn du in einem Zyklus der Länge k > 25 bist. Für einen Zyklus der Länge k muss man k Fächer auswählen, das sind A(k) = (n über k) Möglichkeiten. Wenn man sich einigt, dass das kleinste Element immer den Zyklus startet, kann man die restlichen k-1 beliebig anordnen. Das ergibt Z(k) = (k-1)! mögliche Zyklen, die man aus den k ausgewählten Fächern machen kann. Die restlichen n-k Fächer dürfen beliebig angeordnet sein, das sind R(k) = (n-k)! Möglichkeiten. Also gibt es für einen Zyklus der Länge k > 25 genau: L(k) =A(k) * Z(k) * R(k). Die Wahrscheinlichkeit in so einem Zyklus zu sein ist genau p(k) = k/n. Da die verschiedenen Zykluslängen über 25 nie gemeinsam (in einer Anordnung) auftreten, ist die Wahrscheinlichkeit, in einem zu langen Zyklus zu sein:

Sum(k=26 bis 50, p(k) * L(k)/M)
= Sum(k=26 bis 50, k/n * (n über k) * (k-1)! * (n-k)! / n!)
= Sum(k=26 bis 50, k/n * (1/k!) * (k-1)!)
= Sum(k=26 bis 50, k/n * (1/k))
= Sum(k=26 bis 50, 1/n)
= Sum(k=26 bis 50, 1)/n = 25/50 = 0.5

[Zentimeter]

Danke dir für die ausführliche Antwort!
Ich hatte es schon so vermutet, aber mit der Vermutung alleine liegt man bei solchen Rätseln ja oft daneben!

[rohezal]

Das würde nicht funktionieren wenn 2+ Leute in einer Zelle wären oder?

Beispiel: Zelle 1 hat G1 und G5.

G1 sucht:

F1 -> F4 -> G5 (was Fach 1 Bedeutet). So wären "loops" drin die nicht die richtige Lösung beinhalten. Aber danke für das tolle Rätsel. Vielleicht kann ich das irgendwann mal in einem Programm einbauen. Ein Informatikstudent^^