matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKnobelaufgabenÜbungsaufgabe Gefängnis
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Knobelaufgaben" - Übungsaufgabe Gefängnis
Übungsaufgabe Gefängnis < Knobelaufgaben < Café VH < Internes < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Knobelaufgaben"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Übungsaufgabe Gefängnis: Übungsaufgabe (aktuell)
Status: (Übungsaufgabe) Aktuelle Übungsaufgabe Status (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

        
Bezug
Übungsaufgabe Gefängnis: dummy-frage
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:52 Di 30.08.2011
Autor: Schadowmaster

auf dass auch alle die Aufgabe sehen.

Bezug
        
Bezug
Übungsaufgabe Gefängnis: Tipp
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Übungsaufgabe Gefängnis: tipps/push
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:30 Fr 23.09.2011
Autor: Schadowmaster

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

Bezug
                
Bezug
Übungsaufgabe Gefängnis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Übungsaufgabe Gefängnis: Erstaunlich
Status: (Frage) beantwortet Status 
Datum: 01:13 So 25.09.2011
Autor: HJKweseleit

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]

Bezug
                
Bezug
Übungsaufgabe Gefängnis: Antwort
Status: (Antwort) fertig Status 
Datum: 10:40 So 25.09.2011
Autor: Schadowmaster


> 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


Bezug
        
Bezug
Übungsaufgabe Gefängnis: Lösungsansatz
Status: (Frage) beantwortet Status 
Datum: 15:24 So 25.09.2011
Autor: HJKweseleit

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.


Bezug
                
Bezug
Übungsaufgabe Gefängnis: Antwort
Status: (Antwort) fertig Status 
Datum: 15:35 So 25.09.2011
Autor: Schadowmaster

Klingt soweit ganz nett, ja.^^
Dann berechne mal die Wahrscheinlichkeit, dass eine Kette > 50 entsteht. ;)

MfG

Schadow

Bezug
                        
Bezug
Übungsaufgabe Gefängnis: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Knobelaufgaben"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]