www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de