Gefangenenrätsel
Ingmar Rubin
Es gibt einen zentralen Raum, der von keiner der Zellen aus gesehen
werden kann.
Dort befindet sich eine Lampe, die mit einem Schalter ein- bzw.
ausgeschaltet werden kann.
Der Wärter führt jeden Tag einen zufällig ausgewählten Gefangenen in
den Raum.
Dieser darf dort die Lampe beliebig ein- oder ausschalten, sie so
lassen wie sie ist oder oder die Behauptung aufstellen, daß alle 100
schon mal in dem Raum waren. Wenn die Behauptung stimmt,werden die
Gefangenen frei gelassen, sollte sie aber falsch sein, werden alle
erschossen.
Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
einmal treffen, um eine Strategie zu besprechen, danach gibt es keinen
Kontakt mehr.
Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
dass alle noch recht jung sind und keiner vorzeitig stirbt ?
Joachim Pimiskern
Ingmar Rubin schrieb:
> Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
> einmal treffen, um eine Strategie zu besprechen, danach gibt es
> keinen Kontakt mehr.
> Wie können die Gefangenen sicher freikommen, unter der
> Voraussetzung, dass alle noch recht jung sind und keiner
> vorzeitig stirbt ?
Sie sollten für das Treffen den Raum mit der Glühbirne wählen.
Grüße,
Joachim
Hermann Kremer
>100 Gefangene sitzen in einem Gefängnis mit 100 Einzelzellen.
>Es gibt einen zentralen Raum, der von keiner der Zellen aus gesehen
>werden kann.
>Dort befindet sich eine Lampe, die mit einem Schalter ein- bzw.
>ausgeschaltet werden kann.
>Der Wärter führt jeden Tag einen zufällig ausgewählten Gefangenen in
... ist "jeden" in "jeden Tag" eine mathematisch korrekte Feststellung?
>den Raum.
>Dieser darf dort die Lampe beliebig ein- oder ausschalten, sie so
>lassen wie sie ist oder oder die Behauptung aufstellen, daß alle 100
>schon mal in dem Raum waren. Wenn die Behauptung stimmt,werden die
>Gefangenen frei gelassen, sollte sie aber falsch sein, werden alle
>erschossen.
>Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
>einmal treffen, um eine Strategie zu besprechen, danach gibt es keinen
>Kontakt mehr.
>Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
>dass alle noch recht jung sind und keiner vorzeitig stirbt ?
... und die Lampe nicht vorzeitig kaputt geht ...
Gruß
Hermann
--
G. Frege
wrote:
(A) Der Wärter führt jeden Tag einen _zufällig ausgewählten_
Gefangenen in den Raum.
(B) ...die Behauptung aufstellen, daß alle 100 schon mal in dem Raum
waren. Wenn die Behauptung stimmt,werden die Gefangenen frei gelassen.
(C) Wie können die Gefangenen _sicher_ freikommen...?
Also m.E. ist (C) nicht "sicherzustellen" durch (A) und (B). Wenn
tatsächlich jeweils ein _zufällig ausgewählter_ Gefangener in den Raum
geführt wird, kann es ohne weiteres sein, dass der eine oder andere
der Gefangenen NIE in diesen Raum geführt wird. D.h. Die Behauptung,
dass alle 100 schon mal in dem Raum waren, würde NIE richtig sein; die
Gefangenen könnten also _in diesem Fall_ NIE freikommen; also schon
mal gar nicht "sicher".
F.
P.S.
Vielleicht sollte (C) lauten: Welche Möglichkeit gibt es für die
Gefangenen u.U. (also im Idealfall) freizukommen?
Welche Strategie wäre also sinnvoll?
Leonhard Vogt
> Gefangenen u.U. (also im Idealfall) freizukommen?
>
> Welche Strategie wäre also sinnvoll?
Da müssten sich die Gefangenen wohl auf ein akzeptables Risiko einigen
und zum Beispiel nach einem Jahr soll dann einer die Behauptung wagen.
naja, ein Jahr wäre wohl noch sehr unsicher...
Leonhard
Alfred Flaßhaar
(...)
> Der Wärter führt jeden Tag einen zufällig ausgewählten Gefangenen in
> den Raum.
(...)
Bedeutet hier "zufällig" - gleichwahrscheinlich?
Gruß, Alfred
Klaus Nagel
Ingmar Rubin wrote:
Hallo Ingmar,
das ist ein schönes Rätsel. Ich bringe hier eine Lösung, wer noch
weiterdenken will sollte hier aufhören zu lesen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage, nach 99
fängt er wieder bei Null an. Die Gefangenen werden auch von 0 bis 99
numeriert. Nur dann, wenn die Tageszahl mit seiner Nummer übereinstimmt,
verläßt er den Raum bei brennender Lampe. Betritt jemand den
erleuchteten Raum, dann weiß er, wer am Vortag dort war, und streicht
ihn von seiner Liste. Ist bei einem Gefangenen die Liste vollständig
abgehakt, so meldet er, daß alle da waren.
Bei dieser Methode ist sicher Langlebigkeit gefragt, ich werde es gleich
simulieren und das Ergebnis mitteilen.
Gruß,
Klaus Nagel
Kendzia_Stephan
Ingmar Rubin wrote:
> 100 Gefangene sitzen in einem Gefängnis mit 100 Einzelzellen.
> Es gibt einen zentralen Raum, der von keiner der Zellen aus gesehen
> werden kann.
Es kann also nicht gesehen werden, ob in diesem Raum "Licht an"
oder "Licht aus" ist?
Der einzige Gefangene, der über den jeweils aktuellen
Beleuchtungszustand dieses Raumes *für einen Tag* Bescheid weiß,
ist derjenige, der den Raum gerade verlassen hat?
Richtig so?
> Dort befindet sich eine Lampe, die mit einem Schalter ein- bzw.
> ausgeschaltet werden kann.
Wenn es sich verhält wie oben von mir angegeben, hat der
Beleuchtungszustand des Raumes keine Bedeutung.
Oder können die Gefangenen weiterhin irgendwie kommunizieren?
Wenn das Licht in dem Raum von den Zellen aus zu sehen wäre -
wär's kein Problem.
> Der Wärter führt jeden Tag einen zufällig ausgewählten Gefangenen in
> den Raum.
> Dieser darf dort die Lampe beliebig ein- oder ausschalten, sie so
> lassen wie sie ist oder oder die Behauptung aufstellen, daß alle 100
> schon mal in dem Raum waren. Wenn die Behauptung stimmt,werden die
> Gefangenen frei gelassen, sollte sie aber falsch sein, werden alle
> erschossen.
> Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
> einmal treffen, um eine Strategie zu besprechen, danach gibt es keinen
> Kontakt mehr.
> Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
> dass alle noch recht jung sind und keiner vorzeitig stirbt ?
Wie kodiere ich im Beleuchtungszustand: "Ich war schonmal hier"
bzw. "Ich war das erste Mal hier" für den jeweiligen Nachfolger?
Das ist wohl hier die Frage.
Mal sehen.*knobel*
Stephan
Kendzia_Stephan
Klaus Nagel wrote:
[...]
> Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage, nach 99
> fängt er wieder bei Null an. Die Gefangenen werden auch von 0 bis 99
> numeriert. Nur dann, wenn die Tageszahl mit seiner Nummer übereinstimmt,
> verläßt er den Raum bei brennender Lampe. Betritt jemand den
> erleuchteten Raum, dann weiß er, wer am Vortag dort war,
DAS braucht er nicht zu wissen, kann es auch nicht. Es reicht
aber, wenn er weiß, dass der vorige einer war der an "seinem"
Tag drin war - und kann also einen weiteren Strich auf seiner
Liste machen.
Auf die Schnelle sehe ich aber eine Schwierigkeit:
Wie, wenn nun an *zwei oder mehr* aufeinanderfolgenden Tagen
jeweils Gefangene an "ihrem" Tag ins Zimmer kommen?
Sie finden es beleuchtet vor - und verlassen es auch so.
ABER der einzelne Gefangene hat keine Information darüber, ob
das Licht nicht schon seit dem vor-vorigen Mal brennt!
Deshalb funktioniert die Methode tatsächlich nur bei *einem*
Gefangenen - der muss dann bei der Anfangsbesprechung quasi als
"Melder" ausgewählt werden -, und der muss *selbst* *mindestens*
100mal in den Raum gerufen werden, damit überhaupt erst einmal
eine Chance *anfängt* zu bestehen.
Also: Langlebigkeit ist gefragt - wie Du schon richtig sagtest!
Gruß
Stephan
Kendzia_Stephan
Klaus Nagel wrote:
[...]
Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage,
nach 99 fängt er wieder bei Null an. Die Gefangenen werden auch
von 0 bis 99 numeriert. Nur dann, wenn die Tageszahl mit seiner
Nummer übereinstimmt, verläßt er den Raum bei brennender Lampe.
Betritt jemand den erleuchteten Raum, dann weiß er, wer am
Vortag dort war,
DAS braucht er nicht zu wissen, kann es auch nicht. Es reicht
Pether Hubert
>> Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage,
>> nach 99 fängt er wieder bei Null an. Die Gefangenen werden auch von
>> 0 bis 99 numeriert. Nur dann, wenn die Tageszahl mit seiner Nummer
>> übereinstimmt, verläßt er den Raum bei brennender Lampe. Betritt
>> jemand den erleuchteten Raum, dann weiß er, wer am Vortag dort war,
> DAS braucht er nicht zu wissen, kann es auch nicht. Es reicht aber,
> wenn er weiß, dass der vorige einer war der an "seinem" Tag drin war
> - und kann also einen weiteren Strich auf seiner Liste machen.
Warum kann er nicht wissen, _wer_ in dem Raum war? Jeder kennt eines
jeden Nummer und jeder kennt die Nummer des jeweiligen Tages. Also
weiss er, wer am vortag in dem Raum war.
> Auf die Schnelle sehe ich aber eine Schwierigkeit: Wie, wenn nun an
> *zwei oder mehr* aufeinanderfolgenden Tagen jeweils Gefangene an
> "ihrem" Tag ins Zimmer kommen? Sie finden es beleuchtet vor - und
> verlassen es auch so. ABER der einzelne Gefangene hat keine
> Information darüber, ob das Licht nicht schon seit dem vor-vorigen
> Mal brennt!
Das macht doch nichts. Der Gefangene, der das Licht brennend
vorfindet, weiss nur, wer am Vortag da war und kann diesen abhaken.
Der vom vovorigen Tag wurde vom Gefangenen des Vortages abgehakt.
Ciao,
Pether
--
Schlafe niemals mit der Frau deines Bosses, es sei denn, Du bezahlt
ihn zuerst. (Erwerbsregel 110)
Kendzia_Stephan
Klaus Nagel wrote:
[...]
>Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die
>Tage, nach 99 fängt er wieder bei Null an. Die Gefangenen
>werden auch von 0 bis 99 numeriert. Nur dann, wenn die
>Tageszahl mit seiner Nummer übereinstimmt, verläßt er den
>Raum bei brennender Lampe. Betritt jemand den erleuchteten
>Raum, dann weiß er, wer am Vortag dort war,
DAS braucht er nicht zu wissen, kann es auch nicht. Es reicht
aber, wenn er weiß, dass der vorige einer war der an "seinem"
Tag drin war - und kann also einen weiteren Strich auf seiner
Liste machen.
Auf die Schnelle sehe ich aber eine Schwierigkeit:
Wie, wenn nun an *zwei oder mehr* aufeinanderfolgenden Tagen
jeweils Gefangene an "ihrem" Tag ins Zimmer kommen?
Sie finden es beleuchtet vor - und verlassen es auch so.
ABER der einzelne Gefangene hat keine Information darüber, ob
das Licht nicht schon seit dem vor-vorigen Mal brennt!
Deshalb funktioniert die Methode tatsächlich nur bei *einem*
Klaus Nagel
Kendzia_Stephan wrote:
>
>
> Klaus Nagel wrote:
> [...]
>
>> Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage, nach
>> 99 fängt er wieder bei Null an. Die Gefangenen werden auch von 0 bis
>> 99 numeriert. Nur dann, wenn die Tageszahl mit seiner Nummer
>> übereinstimmt, verläßt er den Raum bei brennender Lampe. Betritt
>> jemand den erleuchteten Raum, dann weiß er, wer am Vortag dort war,
>
>
> DAS braucht er nicht zu wissen, kann es auch nicht.
Wenn ich am Tag 47 eine brennende Lampe vorfinde, weiß ich, daß der
Gefangene 46 am Vortag dort war. Dabei spielt es keine Rolle, ob auch
Nummer 46 Licht vorgefunden hat; er wüßte dann eben, daß 45 unmittelbar
vor ihm da war, und könnte ihn abhaken. Und wenn ich Nummer 47 bin,
lasse ich das Licht brennen, sonst mache ich es aus.
> Also: Langlebigkeit ist gefragt - wie Du schon richtig sagtest!
100 Simulationen lieferten einen Durchschnitt von 2995792 Tagen, das
sind über 82000 Jahre. Die kürzeste Dauer war 2497104 Tage, die längste
3441307.
Gruß,
Klaus Nagel
Kendzia_Stephan
Pether Hubert wrote:
> Kendzia_Stephan <s-ke...@gmx.de> writes:
>
>>>Vom Besprechungstag (Tag 0) an zählt jeder Gefangenen die Tage,
>>>nach 99 fängt er wieder bei Null an. Die Gefangenen werden auch von
>>>0 bis 99 numeriert. Nur dann, wenn die Tageszahl mit seiner Nummer
>>>übereinstimmt, verläßt er den Raum bei brennender Lampe. Betritt
>>>jemand den erleuchteten Raum, dann weiß er, wer am Vortag dort war,
>>
>>DAS braucht er nicht zu wissen, kann es auch nicht. Es reicht aber,
>>wenn er weiß, dass der vorige einer war der an "seinem" Tag drin war
>>- und kann also einen weiteren Strich auf seiner Liste machen.
>
>
> Warum kann er nicht wissen, _wer_ in dem Raum war? Jeder kennt eines
> jeden Nummer >und jeder kennt die Nummer des jeweiligen Tages. Also
> weiss er, wer am vortag in dem Raum war.
Naja gut, aber er weiß nur das "Wer" als Nummer - was aber ja
völlig ausreicht.
>>Auf die Schnelle sehe ich aber eine Schwierigkeit: Wie, wenn nun an
>>*zwei oder mehr* aufeinanderfolgenden Tagen jeweils Gefangene an
>>"ihrem" Tag ins Zimmer kommen? Sie finden es beleuchtet vor - und
>>verlassen es auch so. ABER der einzelne Gefangene hat keine
>>Information darüber, ob das Licht nicht schon seit dem vor-vorigen
>>Mal brennt!
>
>
> Das macht doch nichts. Der Gefangene, der das Licht brennend
> vorfindet, weiss nur, wer am Vortag da war und kann diesen abhaken.
> Der vom vovorigen Tag wurde vom Gefangenen des Vortages abgehakt.
Richtig. Deshalb kann erst dann ein Gefangener in die Lage
kommen, diese befreiende Aussage zu machen, wenn *er*
persönlich auf *seiner* Liste alle abgehakt hat.
Der Zeitpunkt, wo alle mindestens einmal drangewesen waren, mag
indes schon wesentlich früher gekommen sein - nur weiß man
nichts davon.
Deshal wird#s wohl einige Zeit dauern.
Es lässt sich übrigens sicherlich eine
Wahrscheinlichkeitsrechnung anstellen, wann durchschnittlich
(also noch wieviel Tagen) alle sicher frei kommen.
Gruß
Stephan
>
> Ciao,
>
> Pether
Roland Mosler
> Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
> einmal treffen, um eine Strategie zu besprechen, danach gibt es keinen
> Kontakt mehr.
> Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
> dass alle noch recht jung sind und keiner vorzeitig stirbt ?
Abgesehen von der Lösung von Klaus Nagel hier zwei weitere:
1. Beim ersten Besuch in dem Zimmer wird ein Kratzer in die Lampe gemacht.
2. Der Zellentrakt ist aus den Zellen einsehbar.
Gruß,
Roland
--
Schottland, Island und Türkei neu auf http://www.Jorga-Interactive.de/Reisen
Pether Hubert
> Naja gut, aber er weiß nur das "Wer" als Nummer - was aber ja völlig
> ausreicht.
Zum einen reicht das, wie Du richtig sagst, voellig aus, zum anderen
kann es durchaus sein, dass ein jeder auch den Namen der jeweiligen
Nummern kennt. Wer 82000 Jahre lebt, hat vielleicht auch ein gutes
Gedaechtnis und kann sich Nummernzuordnungen von 100 Gefangenen
merken.
> Richtig. Deshalb kann erst dann ein Gefangener in die Lage kommen,
> diese befreiende Aussage zu machen, wenn *er* persönlich auf
> *seiner* Liste alle abgehakt hat.
Genau. Niemand hat je etwas anderes behauptet.
> Der Zeitpunkt, wo alle mindestens einmal drangewesen waren, mag
> indes schon wesentlich früher gekommen sein - nur weiß man nichts
> davon.
Das ist halt der Preis, den man fuer diese Sicherheit bezahlt.
> Deshal wird#s wohl einige Zeit dauern. Es lässt sich übrigens
> sicherlich eine Wahrscheinlichkeitsrechnung anstellen, wann
> durchschnittlich (also noch wieviel Tagen) alle sicher frei kommen.
Naja, aber da spielst Du auf Risiko, und es geht immerhin darum, nicht
erschossen zu werden. Was hast Du davon, wenn die Wahrscheinlichkeit,
erschossen zu werden, unter 0.0001 liegt, wenn's dann halt geschieht?
Ciao,
Pether
--
Halte Deine Lügen konsistent. (Erwerbsregel 60)
G. Frege
wrote:
> Es lässt sich übrigens sicherlich eine
> Wahrscheinlichkeitsrechnung anstellen, wann [...]
> (also noch wieviel Tagen) alle sicher frei kommen.
>
Ja. "Am Ende aller Tage". :-)
Will sagen, N Tage (wobei N beliebig ist) reichen nicht aus, um das
_sicher zu stellen_.
Und "im Schnitt" sieht's auch nicht wirklich viel besser aus:
"100 Simulationen lieferten einen Durchschnitt von 2995792
Tagen, das sind über 82000 Jahre." (Klaus Nagel)
Da aber Menschen nun mal in der Regel eher nicht so alt werden, kann
man die vorgeschlagene Methode in der PRAXIS wohl vergessen.
F.
Kendzia_Stephan
> Kendzia_Stephan wrote:
[...]
>> Also: Langlebigkeit ist gefragt - wie Du schon richtig sagtest!
> 100 Simulationen lieferten einen Durchschnitt von 2995792 Tagen, das
> sind über 82000 Jahre. Die kürzeste Dauer war 2497104 Tage, die längste
> 3441307.
Och, das sitzt man doch auf einer Arschbacke ab! :-)
Ich dachte schon, 's würde *richtig* lang dauern...
Stephan
P.S.: Also war meine Idee mit der "Es war jemand zum ersten mal
hier"-Codierung wohl falsch.
Es wäre auch wirklich nicht gegangen, hab's nochmal überprüft.
G. Frege
<BueroFl...@t-online.de> wrote:
>
> Bedeutet hier "zufällig" - gleichwahrscheinlich?
>
Vermutlich. Aber selbst eine Gleichverteilung der Wahrscheinlichkeit
ändert nix daran, dass der eine oder andere Gefangene _u.U._ NIE
ausgewählt wird (sofern die Auswahl des Gefangenen _zufällig_
erfolgt).
Das ist halt das Wesen des Zufalls: weiße Flecken sind immer
_möglich_. (So ist es z.B. [bei zufälliger Auswahl der Gefangenen
_und_ Gleichverteilung] möglich, dass ein und der selbe Gefangene
10000 mal in Folge in den Raum geführt wird; auch wenn das _extrem_
unwahrscheinlich ist.)
F.
Alfred Flaßhaar
Wenn es also eine zwingende Lösung gibt, die eine sinnvolle
Restlebensdauer außerhalb des Gefängnisses verspricht, dann muß der
Lösungsweg unabhängig davon sein, ob irgendein Gefangener nie oder
mehrmals in den Lampenraum gelangt.
Alfred
Klaus Nagel
Klaus Nagel wrote:
> 100 Simulationen lieferten einen Durchschnitt von 2995792 Tagen, das
sind über 82000 Jahre. Die kürzeste Dauer war 2497104 Tage, die
längste 3441307.
Die Tage stimmen, aber es sind nur etwa 8200 Jahre! Das hätte mir
eigentlich nicht passieren dürfen, denn ich arbeite ständig mit dem
Julianischen Datum; das sind die Tage seit 1.1.4713 v. Chr. und das
Julianische Datum für heute ist 2452581, ist also in der gleichen
Größenordnung wie die Simulationsergebnisse.
Gruß,
Klaus Nagel
Ingmar Rubin
Hallo liebe Rätselfreunde !
Das Rätsel stammt von Thorsten Selke. Ich kenne nicht die
Originalllösung.
Die Anmerkungen von Herrn Frege sind sind korrekt. Es gibt genau wegen
der zufälligen Auswahl keinen "sicheren" Weg.
Soviel sei verraten - es gibt bis jetzt wenigstens zwei Strategien :
- bei Strategie A kommen die Gefangenen im günstigsten Fall nach 199
Tagen raus
- bei Strtegie B muß sich jeder Gefangen eine Zahl von 1 .. 100 merken
und die Tage zählen seit der Zusammenkunft, bei diser Variante sind
sie im Idealfall nach 100 Tagen frei ...
Um ungünstigsten Fall dauert es unendlich viele Tage. Man kann zu
jeder Strategie aber eine Erwartungswert berechnen und dieser sollte
innerhalb der Lebenserwartung liegen.
Mit freundlichen Grüßen - I.Rubin
G. Frege
Ähhh... das "Problem" ist nur, dass die Gefangenen nach Voraussetzung
(dann und nur dann?) freigelassen werden, wenn einer
"...die Behauptung aufstellen, daß alle 100 schon mal in dem
Raum waren. Wenn die Behauptung stimmt,werden die Gefangenen
frei gelassen."
Die Behauptung kann aber NUR dann stimmen, wenn tatsächlich alle 100
schon mal im Raum waren; und wie wir gesehen haben, ist es leider
_nicht_ sicher, dass dieser Fall auch wirklich eintritt (- da ja die
Lebenszeit der Leute begrenzt ist).
F.
Alfred Flaßhaar
Ja, es ist nun folgerichtig, daß ein zwingendes Verfahren in endlicher
Zeit nicht möglich ist. Die Annahme, daß eine derartige Lösung möglich
ist, auch wenn ein Gefangener nie zur zufälligen Auswahl des Wärters
gehört, führt zum Widerspruch zur Voraussetzung für die Richtigkeit der
Lösung, daß alle Gefangene (ohne Ausnahme und in endlicher Zeit) den
Raum betreten haben müssen (egal, wodurch das festzustellen wäre). Dafür
sorgt der Zufallsgenerator "Wärter ".
Eine fesselnde Aufgabe. Nur gut, daß sie zum Wochenende gestellt wurde.
Mit Dank und Gruß an Ingmar, Alfred
G. Frege
wrote:
>>
>> Welche Strategie wäre also sinnvoll?
>>
>
> Soviel sei verraten - es gibt bis jetzt wenigstens zwei Strategien :
>
> - bei Strategie A kommen die Gefangenen im günstigsten Fall nach 199
> Tagen raus
>
> - bei Strategie B [...] sind sie im Idealfall nach 100 Tagen frei ...
>
Naja... Hab mir eine kleine Simulation geschrieben; in der Tat sind
(bei zufälliger Auswahl und angenommener Gleichverteilung) _im
Schnitt_ nach 500 Tagen alle Gefangenen in den besagten Raum geführt
worden!
Hier die Ergebnisse einiger Probeläufe:
535
583
474
524
613
554
499
...
Die "Streuung" ist also nicht übermäßig schlimm.
Um das zu belegen: Wieviele Testläufe waren nötig, um auf über 1200
Tage zu kommen; auch hier ein paar Zahlen:
3986
678
2512
446
...
Wieviele Testläufe waren nötig, um auf unter 300 Tage zu kommen; auch
hier ein paar Zahlen:
408
75
193
...
M.a.W. Mit _hoher Wahrscheinlichkeit_ sind nach ca. 1000 Tagen alle
Gefangenen mindestens ein mal in dem besagten Raum gewesen.
Das ist schon mal ein guter Ausgangspunkt für die Lösung des Rätsels.
F.
G. Frege
<BueroFl...@t-online.de> wrote:
> ...Dafür sorgt der Zufallsgenerator "Wärter".
>
Immerhin habe ich folgendes nun (computational) ermittelt:
---> Mit _hoher Wahrscheinlichkeit_ sind nach ca. 1000 Tagen alle
Gefangenen mindestens ein mal in dem besagten Raum gewesen.
Konkret heißt das, dass folgende Anzahlen von Testläufen dazu nötig
waren, dass einmal nach 1000 Tagen immer noch nicht alle Gefangenen in
dem besagten Raum waren:
192
333
79
318
...
Bei > 1300 Tagen sieht das dann in etwa so aus:
5677
977
1903
6080
...
Die Wahrscheinlichkeit, dass bis dahin schon mal alle in dem Raum
waren, steigt _rapide_ an.
M.a.W. es ist durchaus _realistisch_ anzunehmen, dass die Leute
allesamt nach ca. 1000 Tagen mindestens einmal in dem besagten Raum
waren. (Nimmt man einen Zeitraum von 1500 Tagen, kann man [bei
zufälliger Auswahl und angenommener Gleichverteilung] von einer "an
Sicherheit grenzenden Wahrscheinlichkeit" sprechen.)
Alfred Flaßhaar
Wenn also kein Theoretiker unter den Gefangenen ist, der die
Aussichtslosigkeit der Lage wissenschaftlich begründet und die Hoffnung
trübt, dann sind demnach die praktischen/realen Chancen für einen Erfolg
recht gut. Starkes Argument, Deine Berechnung.
Alfred
Roland Mosler
> Die Tage stimmen, aber es sind nur etwa 8200 Jahre! Das hätte mir
> eigentlich nicht passieren dürfen, denn ich arbeite ständig mit dem
> Julianischen Datum; das sind die Tage seit 1.1.4713 v. Chr. und das
Mit Date::Calc hat man i.A. keine solche Probleme. :-)
(Ist generell bei Datumsberechnungen zu empfehlen)
Paul Ebermann
> "G. Frege" schrieb:
[...]
> > Das ist halt das Wesen des Zufalls: weiße Flecken sind immer
> > _möglich_. (So ist es z.B. [bei zufälliger Auswahl der Gefangenen
> > _und_ Gleichverteilung] möglich, dass ein und der selbe Gefangene
> > 10000 mal in Folge in den Raum geführt wird; auch wenn das _extrem_
> > unwahrscheinlich ist.)
>
> Wenn es also eine zwingende Lösung gibt, die eine sinnvolle
> Restlebensdauer außerhalb des Gefängnisses verspricht, dann muß der
> Lösungsweg unabhängig davon sein, ob irgendein Gefangener nie oder
> mehrmals in den Lampenraum gelangt.
Wenn irgend ein Gefangener nie in den Lampenraum
gelangt, kommen die Gefangenen nie frei (da dann
die Behauptung, es wären schon alle dagewesen,
immer falsch ist.)
Paul
Alfred Flaßhaar
Das wurde inzwischen geklärt.
Alfred
Klaus Nagel
Roland Mosler wrote:
> Klaus Nagel schrieb in de.sci.mathematik:
>
>
>>Die Tage stimmen, aber es sind nur etwa 8200 Jahre! Das hätte mir
>>eigentlich nicht passieren dürfen, denn ich arbeite ständig mit dem
>>Julianischen Datum; das sind die Tage seit 1.1.4713 v. Chr. und das
>>
>
> Mit Date::Calc hat man i.A. keine solche Probleme. :-)
> (Ist generell bei Datumsberechnungen zu empfehlen)
>
Ohne Taschenrechner hätte ich auch kein solches Problem gehabt. :-)
Gruß,
Klaus Nagel
G. Frege
wrote something.
Ahhh... nun habe ich (denke ich) die korrekte Formulierung:
>
> Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
> dass a) alle noch recht jung sind und keiner vorzeitig stirbt...
>
b) und alle Gefangenen wirklich mind. einmal in den besagten
Raum geführt worden sind?
Right?
Dass die Annahme b) durchaus nicht unrealistisch ist [sofern a)
zutrifft], habe ich ja "rechnerisch" (mit dem Rechner) nachgeprüft.
F.
Rainer Rosenthal
Klaus Nagel wrote
> ... ich arbeite ständig mit dem Julianischen Datum;
> das sind die Tage seit 1.1.4713 v. Chr. und das
> Julianische Datum für heute ist 2452581,
Hallo Klaus,
wenn schon, denn schon: kannst Du bitte kurz erzählen,
wieso ausgerechnet dieses Datum als Startpunkt genommen
wurde? Moses' Geburtstag oder so was?
Danke und Gruss,
Rainer
-
Rainer Rosenthal
r.ros...@web.de
juergen
wrote:
>Hallo liebe Rätselfreunde !
>Das Rätsel stammt von Thorsten Selke. Ich kenne nicht die
>Originalllösung.
>Die Anmerkungen von Herrn Frege sind sind korrekt. Es gibt genau wegen
>der zufälligen Auswahl keinen "sicheren" Weg.
Ausgemommen der Fall das sagen wir prisoner #67 nie oder 10000 Tage
nicht ausgewählt wird , ähnlich wie dass beim Roulette an einem
Spieltisch lange nicht die "13" kommt kann man sagen:
Wenn ich zum ersten mal reinkomme mache ich Licht an, sonst immer
ausmachen oder lassen.
Irgendwann wird der Schalter nicht mehr betaetigt, das ist das Signal
für den der das 3 te oder 4te mal (nach Absprache) reinkommt.
Wenn er es an der Verstaubtheit der Schalter sieht.
Ist noch nicht astrein aber so ähnlich...
J
Klaus Nagel
Ingmar Rubin schrieb:
>
> Soviel sei verraten - es gibt bis jetzt wenigstens zwei Strategien :
>
> - bei Strategie A kommen die Gefangenen im günstigsten Fall nach 199
Tagen raus
>
Strategie A scheint ja bedeutend besser zu sein als mein Vorschlag
(siehe Beitrag 2.11 14:22), für den Simulationen eine Dauer von einigen
Tausend Jahren lieferten!
Da liegt die Zusatzfrage nahe:
"Wieviel Tage dauert es im günstigsten Fall bei meinem Verfahren ?"
Ich wünsche einen schönen Sonntag,
Klaus Nagel
Klaus Nagel
Rainer Rosenthal wrote:
> kannst Du bitte kurz erzählen,
> wieso ausgerechnet dieses Datum als Startpunkt genommen
> wurde? Moses' Geburtstag oder so was?
Hallo Rainer,
in anderen Quellen habe ich auch den 23. November 4713 v.Chr. als
Anfangstag gefunden.
Hier sind drei Seiten im Netz zu dem Thema:
www.bautz.de/bbkl/s/s1/scaliger_j_j.shtml
www.ortelius.de/kalender/jd_de.html
www.koenigsmuenster.de/rsk/julianischesdatum.htm
Einen schönen Sonntag,
Klaus
Rainer Rosenthal
Klaus Nagel wrote
>
> in anderen Quellen habe ich auch den 23. November 4713 v.Chr. als
> Anfangstag gefunden.
> Hier sind drei Seiten im Netz zu dem Thema:
>
> www.bautz.de/bbkl/s/s1/scaliger_j_j.shtml
>
> www.ortelius.de/kalender/jd_de.html
>
> www.koenigsmuenster.de/rsk/julianischesdatum.htm
>
Hallo Klaus,
schönen Dank für die Links, die ich gleich mal aufgesucht habe.
Im zweiten davon habe ich die Kerninformation gefunden, die
aussagt, dass kein geschichtliches Ereignis sondern ein rechnerisch
günstiger Zeitpunkt gewählt worden war, um zum Jahr 4713 v. Chr.
zu gelangen:
Der 1540 in Frankreich geborene Gelehrte Joseph Justus Scaliger
schlug im Jahre 1583 eine fortlaufende Zählung der Tage innerhalb
einer "Julianischen Periode" vor. Diese Periode hat eine Länge von
7980 Jahren und stellt das kleinste gemeinsame Vielfache von Mond-
zyklus (19 Jahre), Sonnenzyklus (28 Jahre) und der Indiktion
(15 Jahre) dar. Das Jahr 4713 v.u.Z. ist das erste in allen drei
Zyklen, daher beginnt die Zählung am 1. Januar 4713 v.u.Z. Angaben
im Julianischen Datum werden durch die nachgestellten Buchstaben
"JD" bezeichnet.
Dieser zweite Link scheint überhaupt eine sehr gute Adresse zum
Thema "Kalender" zu sein. Danke.
Aus dem ersten Link habe ich entnommen, dass Scaliger trotz seiner
Pfiffigkeit ein Gegner der Gregor'schen Kalenderreform war.
Klaus Nagel
Ingmar Rubin wrote:
> 100 Gefangene sitzen in einem Gefängnis mit 100 Einzelzellen. Es
> gibt einen zentralen Raum, der von keiner der Zellen aus gesehen werden
> kann. Dort befindet sich eine Lampe, die mit einem Schalter ein-
> bzw. ausgeschaltet werden kann. Der Wärter führt jeden Tag einen
> zufällig ausgewählten Gefangenen in den Raum. Dieser darf dort die
> Lampe beliebig ein- oder ausschalten, sie so lassen wie sie ist
> oder oder die Behauptung aufstellen, daß alle 100 schon mal in dem
> Raum waren. Wenn die Behauptung stimmt,werden die Gefangenen frei
> gelassen, sollte sie aber falsch sein, werden alle erschossen. Am
> Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich einmal
> treffen, um eine Strategie zu besprechen, danach gibt es keinen Kontakt
> mehr. Wie können die Gefangenen sicher freikommen, unter der
> Voraussetzung, dass alle noch recht jung sind und keiner vorzeitig
> stirbt ?
>
Nur der Gefangene L, der am ersten Tag in den Raum geführt wird, darf
das Licht einschalten. Die anderen brauchen nicht zu wissen, wer L ist.
Am ersten Tag schaltet er es ein. Die anderen GefangenenInnen schalten
das Licht aus, wenn es auch bei ihrem vorherigen Besuch gebrannt hat und
dieser noch keine 100 Tage zurückliegt. Trifft L auf eine brennende
Lampe und sind genau 99 Tage seit dem Einschalten vergangen - seine
eigenen Besuchstage nicht mitgezählt -, dann kann er melden, daß alle
Gefangenen mindestens einmal im Raum waren. Kommt L in den dunklen Raum,
dann schaltet er das Licht erst bei einem der nächste Besuche ein, wenn
dieser mindestens 100 Tage später liegt.( Diese Hunderttageregel ist
nicht notwendig, aber sie beschleunigt das Verfahren - jedenfalls
vermute ich das). Am Anfang gilt eine Sonderregelung: Wer außer L - am
Tag 99 das Licht eingeschaltet findet, kann die Vollzähligkeit melden,
in diesem Fall - er hat eine Wahrscheinlichkeit von etwa 10^(-42) - sind
die Gefangenen schon in 100 Tagen frei.
Die 8000 Jahre bei der ersten Strategie sind nur ein Wimpernzucken gegen
die über 10^40 Jahre, die beim zweiten Verfahren zu erwarten sind.
Gruß,
Klaus Nagel
Stefan Kirchner
> Naja... Hab mir eine kleine Simulation geschrieben; in der Tat sind
> (bei zufälliger Auswahl und angenommener Gleichverteilung) _im
> Schnitt_ nach 500 Tagen alle Gefangenen in den besagten Raum geführt
> worden!
>
> Hier die Ergebnisse einiger Probeläufe:
>
> 535
> 583
> 474
> 524
> 613
> 554
> 499
> ...
Das kannst Du auch recht einfach ausrechnen:
Seien X_0, ..., X_n-1 jeweils die Anzahl Tage in einer Phase. Die Phase X_i
hoert auf, wenn einer zum ersten mal den Raum betritt. Danach faengt die
Phase X_i+1 an. Dann gilt
P[in der i.ten Phase kommt jemand neues in den Raum] = (n-i)/n
E[X_i] = n/(n-i)
Damit ergibt sich
E[Anzahl Tage, so dass jeder war mal im Raum war]
= E[X_0 + ... + X_n]
= E[X_0] + ... + E[X_n_1]
= \sum_i=0^n-1 = n/(n-i)
= n* \sum_i=0^n-1 = 1/(n-i)
= n* \sum_j=1^n = 1/j
= n* H_n [n.te harmonische Zahl]
= n * ( ln(n) + 0.5772...) [Eulersche Konstante]
Fuer n = 100 sind das dann im Erwartungswert 518 Tage.
Gruss Stefan
Hermann Kremer
... und hier sind noch einige Links ...
http://scienceworld.wolfram.com/astronomy/JulianDate.html
http://scienceworld.wolfram.com/astronomy/Calendar.html
http://webexhibits.org/calendars/calendar-christian.html
http://serendipity.magnet.ch/hermetic/cal_stud/jdn.htm
http://www.pauahtun.org/julian_period.html
http://quasar.as.utexas.edu/BillInfo/JulianDatesG.html
... und hier der Zusammenhang mit dem openVMS der guten alten
DEC-VAX:
http://www.kgb.com/calend.html
Grüße
Hermann
--
>Einen schönen Sonntag,
>Klaus
>
Marko Renner
> 100 Gefangene sitzen in einem Gefängnis mit 100 Einzelzellen.
> Es gibt einen zentralen Raum, der von keiner der Zellen aus gesehen
> werden kann.
> Dort befindet sich eine Lampe, die mit einem Schalter ein- bzw.
> ausgeschaltet werden kann.
> Der Wärter führt jeden Tag einen zufällig ausgewählten Gefangenen in
> den Raum.
> Dieser darf dort die Lampe beliebig ein- oder ausschalten, sie so
> lassen wie sie ist oder oder die Behauptung aufstellen, daß alle 100
> schon mal in dem Raum waren. Wenn die Behauptung stimmt,werden die
> Gefangenen frei gelassen, sollte sie aber falsch sein, werden alle
> erschossen.
> Am Anfang ist die Lampe ausgeschaltet und die Gefangenen dürfen sich
> einmal treffen, um eine Strategie zu besprechen, danach gibt es keinen
> Kontakt mehr.
> Wie können die Gefangenen sicher freikommen, unter der Voraussetzung,
> dass alle noch recht jung sind und keiner vorzeitig stirbt ?
Die Gefangenen bestimmen einen Zähler. Dieser zählt jedesmal, wenn
er die Lampe eingeschaltet vorfindet, eins weiter und schaltet die
Lampe aus, ansonsten tut er nichts. Alle andere schalten das erste mal,
wenn sie die Lampe ausgeschaltet vorfinden, diese ein, ansonsten tun
sie nichts.
Erwartungswert: 10417,7377518 Tage (28,54 Jahre)
(100/99+100/98....+100/2+100/1 + +99*100)
Moses
G. Frege
<kirc...@informatik.hu-berlin.de> wrote:
>
> Das kannst Du auch recht einfach ausrechnen...
>
> Fuer n = 100 sind das dann im Erwartungswert 518 Tage.
>
Danke, das ist in der Tat recht hilfreich. [ "Aber wozu rechnen, wo
man das doch programmieren kann?" ;-) ]
F.
P.S.
Im Ernst jetzt. Mich hat nicht nur der Erwartungswert interessiert,
sondern u.a. auch die "Streuung" der einzelnen "Testläufe". (Oder hast
Du da auch gleich noch ne weitere Formel zur Hand?)
Bzw. auch die Fragen: Wieviele Testläufe sind nötig, um auf über m
(unter n) Tage zu kommen.