Übungsaufgabe Gefängnis < Knobelaufgaben < Café VH < Internes < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 16:36 Di 30.08.2011 | | Autor: | Schadowmaster |
Hmm, es gab seit fast zwei Monaten keine Übungsaufgabe mehr? oO
Dann ist es wohl mal wieder an der Zeit.
@ Mods: Bitte entsprechend kennzeichnen und Leserechte einstellen.
Allen anderen sei erstmal gesagt: Das Rätsel ist (soweit ich das sehe) recht bekannt. Also falls ihr es schon kennt bitte nicht gleich die Lösung verraten.^^
Wer es noch nicht kennt dem empfehle ich ein wenig rumzuknobeln, die Lösung ist wirklich schön.
| Aufgabe | In einem Gefängnis irgendwo auf der Welt sitzen 100 Verbrecher hinter Gittern.
Die Wärter haben sich - als besondere psychische Folter - ein Spiel ausgedacht:
Jeden Tag werden die Gefangenen nacheinander (in täglich ändernder Reihenfolge) in einen von außen nicht einsehbaren Raum geführt.
In diesem stehen auf einem Tisch in einer langen Reihe 100 geschlossene Kisten.
In jeder der Kisten befindet sich der Name eines der Gefangenen.
Nun darf der Gefangene eine Kiste seiner Wahl öffnen, den Namen darin lesen und daraufhin eine weitere Kiste öffnen.
Das ganze geht so lange weiter, bis der Gefangene seinen eigenen Namen gefunden oder aber 50 Kisten erfolglos geöffnet hat.
Daraufhin wird er aus dem Raum geführt und der nächste ist an der Reihe.
Sollten (wider Erwarten der Wächter) an einem Tag alle Gefangenen ihren Namen finden so werden alle frei gelassen.
Sollte auch nur ein einziger seinen Namen nicht finden so müssen sie alle am nächsten Tag (mit neuen Kisten in einer anderen Reihenfolge) wieder antreten.
Während des Spiels werden die Gefangenen voneinander getrennt und haben keine Möglichkeit der Kommunikation; außerhalb der Spielzeiten können sie allerdings miteinander reden.
Zum Glück für die Gefangenen war unter ihnen ein Mathematiker.
Dieser entwickelte ein System, mit dem alle nach einer Woche frei waren.
a)
Wie funktioniert das System des Mathematikers?
(Anmerkung: Es handelt sich hierbei um ein rein mathematisches System, es geht nicht um eine geheime Kommunikation oder einen Betrugsversuch.)
b)
Wie hoch ist die Wahrscheinlichkeit, dass die Gefangenen (nach dem System aus Teil a) ) nach einer Woche frei sind? |
viel Spaß
Schadowmaster
|
|
| |
|
auf dass auch alle die Aufgabe sehen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:29 Di 30.08.2011 | | Autor: | kamaleonti |
Hallo Schadowmaster,
ich kenne die Aufgabe, weswegen ich hier nur ein kleines Stichwort in die Runde werfe, damit sich auch andere daran versuchen können:
Permutationen
LG
|
|
|
| |
|
So, nochmal hochpushen, vielleicht will sich ja doch noch jemand drann versuchen.
Da bisher nix kam hier nochmal ein paar Tipps (wer die Aufgabe erstmal ohne versuchen möchte liest also besser nicht weiter):
- die Aufgabe lässt sich mit elementarer Kombinatorik lösen; keinerlei große böse Formeln oder so erforderlich
- stochastische Abhängigkeit (alle finden den Namen oder keiner)
- Permutation/Zykelschreibweise
und wenn diese Tipps auch noch keine Idee gebracht haben gibt es hier nen ganz bösen Tipp, der zusammen mit denen oben schon fast alles verrät:
Die Wahrscheinlichkeit, dass alle freikommen, errechnet sich als:
$1 - [mm] \summe_{k=51}^{100} \frac{1}{k}$
[/mm]
Mal sehen, ob jemand mit den Tipps (oder vielleicht auch ohne) eine Lösung hinbekommt...
viel Spaß
Schadowmaster
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:49 Di 04.10.2011 | | Autor: | felixf |
Moin!
> - stochastische Abhängigkeit (alle finden den Namen oder
> keiner)
Das stimmt nicht ganz: es ist durchaus moeglich, dass 51 Leute ihren Namen nicht finden (weil es einen Zykel der Laenge 51 gibt und alle 51 Mitglieder so anfangen, dass sie ihren Namen eben nicht erwischen), jedoch alle anderen 49 Leute ihren Namen finden.
LG Felix
|
|
|
| |
|
Jeden Tag werden die Gefangenen nacheinander (in täglich ändernder Reihenfolge) in einen von außen nicht einsehbaren Raum geführt.Die Gefangenen haben also keinen Einfluss auf ihre Reihenfolge, denn offenbar dürfen sie beispielsweise nicht einmal entscheiden, ihre Reihenfolge vom Vortag beizubehalten.
An jedem Tag ist die Reihenfolge der Kisten ebenfalls anders. Vermutlich können die Gefangene auch nicht erkennen, welche Kisten ihre Vorgänger bereits geöffnet haben.
Findet jemand seinen Namen in einer Kiste, wird diese offenbar nicht einmal entfernt, so dass der Nächste diese Kiste ebenfalls wählen kann.
Eine Kommunikation während des Durchmarsches findet nicht statt.
Die Gefangenen können somit nur entscheiden, welche Kiste jeder öffnen soll. Das einzig wichtige ist somit, dass z.B. nicht alle Gefangenen die ersten 50 Kisten öffnen, denn in diesen können nicht alle 100 verschiedenen Namen sein. Nummeriert man alle Gefangenen und alle Kisten durch und stellt alle Kisten in Gedanken im Kreis auf, so sollte jeder Gefangene mit seiner Nummer beginnen. Dann werden alle Kisten mit der selben Häufigkeit geöffnet. Die W. für die Befreiung betrüge dann aber nur [mm] 0,5^{100}.
[/mm]
|
|
|
| |
|
> Jeden Tag werden die Gefangenen nacheinander (in täglich
> ändernder Reihenfolge) in einen von außen nicht
> einsehbaren Raum geführt.Die Gefangenen haben also keinen
> Einfluss auf ihre Reihenfolge, denn offenbar dürfen sie
> beispielsweise nicht einmal entscheiden, ihre Reihenfolge
> vom Vortag beizubehalten.
>
> An jedem Tag ist die Reihenfolge der Kisten ebenfalls
> anders. Vermutlich können die Gefangene auch nicht
> erkennen, welche Kisten ihre Vorgänger bereits geöffnet
> haben.
>
> Findet jemand seinen Namen in einer Kiste, wird diese
> offenbar nicht einmal entfernt, so dass der Nächste diese
> Kiste ebenfalls wählen kann.
>
> Eine Kommunikation während des Durchmarsches findet nicht
> statt.
>
> Die Gefangenen können somit nur entscheiden, welche Kiste
> jeder öffnen soll. Das einzig wichtige ist somit, dass
> z.B. nicht alle Gefangenen die ersten 50 Kisten öffnen,
> denn in diesen können nicht alle 100 verschiedenen Namen
> sein. Nummeriert man alle Gefangenen und alle Kisten durch
> und stellt alle Kisten in Gedanken im Kreis auf, so sollte
> jeder Gefangene mit seiner Nummer beginnen. Dann werden
> alle Kisten mit der selben Häufigkeit geöffnet. Die W.
> für die Befreiung betrüge dann aber nur [mm]0,5^{100}.[/mm]
Stimmt soweit schonmal.
Allerdings beginnen die Gefangenen bei dir mit ihrem Namen, ziehen danach aber beliebig.
Bedenke, dass die Gefangenen, wenn sie eine Kiste öffnen, den Namen darin lesen dürfen.
MfG
Schadow
|
|
|
| |
|
Dann versuche ich mal folgenden Ansatz:
Jeder, der den Raum betritt, wählt die Kiste mit seiner Nummer. Darin findet er einen Namen, dessen Nummer er auch kennt. Ist es seiner, ist er fertig, ist es ein anderer, so guckt er als nächstes in die Kiste mit der entsprechenden Nummer usw. Er durchläuft damit eine Kette von aufeinander folgenden Nummern, von denen er weder den Einstiegspunkt noch die Länge kennt. Schließt sich diese Kette vor dem 50. Mal, so hat er dann seine eigene Nummer (mit der er ja angefangen hat)gezogen und damit sein Ziel erreicht. In diesem Fall zieht z.B. Gefangener Nr.36 in Kiste Nr.78 die Zahl 36, würde dann wieder auf seinen Startplatz 36 ziehen.
Ob die ganze Sache Erfolg hat, hängt damit einzig und allein davon ab, wie lang die Ketten sind, die durch Permutation der Kisten entstehen, und wo die Einstiegspunkte liegen:
Sind alle Ketten, die durch die Lage der Kisten für jeden Tag festliegen, kürzer als 51, so stoßen alle Gefangenen auf ihren Namen.
Gibt es längere Ketten - und davon kann es dann nur eine geben - , so kann kein Erfolg eintreten. Somit muss man nur die W. dafür berechnen, dass eine Kette mit mehr als 50 Zahlen entsteht.
|
|
|
| |
|
Klingt soweit ganz nett, ja.^^
Dann berechne mal die Wahrscheinlichkeit, dass eine Kette > 50 entsteht. ;)
MfG
Schadow
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:45 Di 04.10.2011 | | Autor: | felixf |
Moin,
> Klingt soweit ganz nett, ja.^^
> Dann berechne mal die Wahrscheinlichkeit, dass eine Kette
> > 50 entsteht. ;)
damit das endlich mal fertig wird 
Eine Permutation von [mm] $\{ 1, \dots, 100 \}$ [/mm] hat hoechstens einen Zyklus der Laenge $> 50$.
Die Anzahl der Permutationen mit einem Zyklus der Laenge $k [mm] \in [/mm] [51, 100]$ ist [mm] $\binom{100}{k} [/mm] = [mm] \frac{100!}{k! (100 - k)!}$ [/mm] (Anzahl der Positionen, die der Zykel durchlaeuft) mal [mm] $|S_{100 - k}| [/mm] = (100 - k)!$ (Anzahl der Moeglichkeiten, die restlichen $100 - k$ Felder zu fuellen) mal [mm] $|S_k| [/mm] / k$ (Anzahl der $k$-Zyklen mit den Eintraegen [mm] $\{ 1, \dots, k \}$).
[/mm]
Damit gibt es also [mm] $\binom{100}{k} |S_{100 - k}| |S_k| [/mm] / k = [mm] \frac{100!}{k}$ [/mm] solche Permutationen.
Die gesuchte Wahrscheinlichkeit ist also $1 - [mm] \frac{1}{|S_{100}|} \sum_{k=51}^{100} \frac{100!}{k} [/mm] = 1 - [mm] \sum_{k=51}^{100} \frac{1}{k} \approx [/mm] 0.3118$. Der Erwartungswert der Anzahl Tage, bis wann alle Gefangenen frei sind, ist also [mm] $\approx [/mm] 3.21$, und die Wahrscheinlichkeit, dass dies innerhalb von sieben Tagen passiert, ist [mm] $\approx [/mm] 0.9629$ (geometrische Verteilung).
LG Felix
|
|
|
|
