Gefangenenrätsel
g.j.wo...@math.utwente.nl
=====================================================
Aus de.sci.mathematik,
von Ingmar Rubin <ing...@matheraetsel.de>
=====================================================
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 ?
--
GJ Woeginger http://www.math.utwente.nl/~woeginge/
Hannes Schlichting
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> Wie können die Gefangenen sicher freikommen, unter der
> Voraussetzung, dass alle noch recht jung sind und keiner vorzeitig
> stirbt ?
Jeder ritzt, sobald er den Raum zum ersten Mal betritt, eine Kerbe irgendwo
in die Wand oder kritzelt mit einem Stift (wenn er einen hat) einen Strich
an eine unauffällige Stelle.
Oder ist das nicht erlaubt?
Dann nehme ich einmal an, daß der Raum zwar nicht einsehbar ist, aber der
Lichtschein schon bis in die Zellen zu sehen ist. Dann schaltet jeder
Gefangene ausschließlich beim ersten Mal die Leuchte 1x ein und wieder aus.
Alle anderen zählen mit und wissen wieviele schon in dem Raum waren.
Bis dann ...
Hannes
Wolfram Helwig
.
.
.
.
.
.
.
.
.
.
.
.
.
.
bei dem Treffen wird ein Gefangener bestimmt, der die Lampe immer
einschaltet, wenn er in den Raum kommt. Alle anderen schalten die Lampe
einmal aus, wenn sie in den Raum kommen und die Lampe an ist. Wenn die Lampe
schon aus ist, oder sie diese schon einmal ausgeschaltet haben machen sie
nichts.
Der Gefangene, der die Lampe immer einschaltet muss mitzählen, wie oft er
sie schon eingeschaltet hat und wenn er sie das 100. mal einschalten würde
kann er sagen, dass schon alle im Raum waren. Da sie alle noch sehr jung
sind macht es ihnen natürlich überhaupt nichts aus, ein paar Jährchen im
Gefängnis zu verbringen.
Ciao
Wolfram
Andreas Riedel
> 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 ?
SPOILER
Wer den Raum zum ersten Mal betritt, betätigt den Schalter. Wer zum
wiederholten Male dort ist, läßt die Lampe, wie sie ist.
Die Gefangenen müssen jetzt nur noch mitzählen, wie oft schon geschaltet
wurde.
Gruß
Andreas
--
Those who desire to give up Freedom in order to gain Security,
will not have, nor do they deserve, either one. (T. Jefferson)
Karsten Buth
absprechen. Und ich kann ja nicht die Schaltung mitzählen, wenn ich gar
nicht im Raum bin. Ich nehm ja nur das vom Raum wahr, was ich dort
selbst sehe. Und als weitere Info hab ich nur die verstrichenen Tage -
also die Anzahl der Raumbesuche.
Gabriel Maresch
verkomplizierung: wie sieht eine strategie aus, wenn man die voraussetzung
fallen läßt, daß man weiß daß die lampe am anfang ausgeschaltet ist?
mfg
gabriel
<g.j.wo...@math.utwente.nl> schrieb im Newsbeitrag
news:aptneq$15a$1...@netlx020.civ.utwente.nl...
Ephrim Khong
Wolfram Helwig schrieb:
Wenn der Wärter das Gespräch mitbekommt dann wird er aber den
"Auserwählten", der die Lampe immer einschaltet, nur ein einziges mal aus
seiner Zelle holen. Gibt es auch einer Strategie, die "sicher" zum Erfolg
führt, also zu der der Wärter keine Gegenstrategie entwickeln kann?
b.
Marko Renner
Quer über den Daumen gepeilt würde ich auf ca. 35 Jahre tippen, mag
jemand nachrechnen?
Moses
Kurt Stege
> Wenn der Wärter das Gespräch mitbekommt dann wird er aber ...
>Gibt es auch einer Strategie, die "sicher" zum Erfolg
>führt, also zu der der Wärter keine Gegenstrategie entwickeln kann?
Der Wärter kann bei den gegebenen Spielregeln keine Gegenstrategie
entwickeln, weil er keinen Einfluß auf das Geschehen hat. Es wurde
ausdrücklich festgelegt, daß ein zufälliger Gefangerer in den Raum
geführt wird, und nicht einer, der vom Wärter ausgewählt wird.
Hätte der Wärter die Wahl, und würde er die Freilassung der Gefangenen
verhindern wollen, würde er einfach den letzten Gefangenen erst
nach 42023 Jahren das erste Mal herausführen.
Gruß,
Kurt.
Kurt Stege
>"Gabriel Maresch" <gmar...@gmx.net> wrote:
>
>>was mich bei diesem rätsel noch interessieren würde ist folgende
>>verkomplizierung: wie sieht eine strategie aus, wenn man die voraussetzung
>>fallen läßt, daß man weiß daß die lampe am anfang ausgeschaltet ist?
>
>Dann fängt man am 2.Tag an, und vereinbart, dass die Lampe am 1.Tag in
>gewünschten Zustand gebracht wird.
Und wenn dann auch noch die Regelung entfernt wird, daß an jedem
Tag genau ein Kandidat in den Lampenraum gebracht wird, und deshalb
der erste nicht weiß, ob er wirklich der erste ist, dann fängt
man mit der Prozedur wieder sofort an, und ...
Spoilerspace
.
.
.
.
.
.
.
.
.
.
.
.
.
der ausgewählte Gefangene meldet nicht beim 100. Mal sondern beim
etwa 199. Mal das Ziel an. Dafür schaltet jeder Gefangene die Lampe
nicht nur beim ersten Mal aus, sondern auch noch ein zweites Mal.
Gruß,
Kurt.
Marko Renner
ausgewählte Gefange die Lampe immer ausschaltet, und jeder andere beim
erstmaligen Vorfinden der ausgeschalteten Lampe diese einschaltet.
> Quer über den Daumen gepeilt würde ich auf ca. 35 Jahre tippen, mag
> jemand nachrechnen?
Nach einigem Überlegen und Rechnen senke ich ab auf 28 Jahre, 9 Monate und
24 Tage. Wohlgemerkt im Durchschnitt, könnte auch länger dauern.
(Der Graf von Monte Christo war schon nach der Hälfte sehr, sehr
rachedurstig. ;-)
Moses
Ephrim Khong
Schon klar, vieleicht habe ich es falsch formuliert. Vieleicht ist es so
etwas einsichtiger:
Nachdem alle 100 Gefangenen einmal zur Lampe gelassen wurde, muss nach
einer endlichen Zeit einer der Gefangenen behaupten dass alle 100 bei der
Lampe waren, unabhängig davon ob die Auswahl der Gefangenen zufällig ist
oder ob der Wärter irgendeine Gegenstrategie entwickelt.
eph
Michael Ganser
> führt, also zu der der Wärter keine Gegenstrategie entwickeln kann?
Wie wäre es mit folgender Gegenstrategie des Wärters: Er erschiesst die
Gefangenen auf JEDEN Fall, egal was sie antworten.
Was ich damit sagen will: man sollte sich an den Wortlaut des Rätsels
halten.
Kurt Stege
>Nachdem alle 100 Gefangenen einmal zur Lampe gelassen wurde, muss nach
>einer endlichen Zeit einer der Gefangenen behaupten dass alle 100 bei der
>Lampe waren, unabhängig davon ob die Auswahl der Gefangenen zufällig ist
>oder ob der Wärter irgendeine Gegenstrategie entwickelt.
Hier habe ich nur die Ahnung, aber (noch) keinen Beweis, daß die
Gefangenen nun keine Chance mehr haben, zumindest nicht, wenn der
Wärter pfiffig ist, die Gefangenen nicht freilassenwill und auch noch
deren Strategie kennt.
Ich leite daher diese interessante Aufgabe an die gesamte Newsgroup
weiter ;-)
Gemeinsam kriegen wir es schon hin, wenn wir nur genügend Stichwörter
und Ansätze hin und her werfen. Damit wurden hier schon viel schwerere
Aufgaben geknackt!
Ich fange schon mal an:
Der Wärter könnte zwei Strategien fahren:
A) 1, 2, 3, ..., 99 rausholen, und ab dem 100. Tag immer die Nummer 100.
B) 2, 2, 3, ..., 99 rausholen, und ab dem 100. Tag immer die Nummer 100.
Im Falle B kann irgendwann mal (nach z.B. 10 Jahren) die Nummer 1 nachgeholt
werden.
In beiden Fällen ist es (innerhalb der ersten 10 Jahre) unabhängig von
der Strategie der Gefangenen immer nur die Nummer 100, die behaupten kann,
es wären inzwischen alle 100 Gefangenen bei der Lampe gewesen. In den ersten
99 Tagen war ja gar nicht genug Zeit, daß jeder bei der Lampe gewesen sein
könnte, und danach kommt nur noch Nummer 100 hin.
Dieser Gefangene 100 kann aber zwischen A) und B) nicht unterscheiden.
Zumindest sehe ich nicht, wie mit der 1-Bit-Lampe genügend Information
übertragen werden kann, ob alle 99 anderen Gefangenen bereits da waren.
(OK, zwischen A und B kann 100 noch unterscheiden; denn zwei Zustände
hat die Lampe ja. Aber ob A oder B oder C läßt sich nicht mehr eindeutig
klären.)
Im Fall A) muß Nummer 100 irgendwann (entweder sofort, oder nach einem
Jahr oder nach 100 Jahren) nach endlicher Zeit bekanntgeben, daß er
die berechtigte Freilassung aller Gefangenen fordert.
Im Fall B) muß Nummer 100 noch beliebig lange warten, bis die fehlende
Nummer 1 nachgeliefert wird. Erst dann darf 1 oder auch die 100 das
Spiel beenden.
Gruß,
Kurt.
Ortwin Gasper
> Nachdem alle 100 Gefangenen einmal zur Lampe gelassen wurde, muss nach
> einer endlichen Zeit einer der Gefangenen behaupten dass alle 100 bei der
> Lampe waren, unabhängig davon ob die Auswahl der Gefangenen zufällig ist
> oder ob der Wärter irgendeine Gegenstrategie entwickelt.
Da gibt es keine Lösung. Wird ein Gefangener an Tag 101 erstmalig in den
Raum geführt, kann er nämlich nicht entscheiden, ob schon alle 100 im
Raum waren. Legt seine Strategie nun fest, daß er, wenn er an den Tagen
102,....,k wieder in den Raum geführt wird, mitteilt, es seien alle 100
im Raum gewesen, kann der Wärter bis Tag 101 weniger als 100 verschiedene
Gefangene in den Raum führen und ab Tag k+1 die 'unverbrauchten' einplanen.
Legt dagegen seine Strategie fest, daß er in keinem Falle, wenn er ab
Tag 101 jeden Tag in den Raum geführt wird, meldet, daß alle 100 im Raum
waren, braucht der Wärter nur mit ihm am Tage 101 die 100 voll zu machen,
und sie sitzen bis in die Ewigkeit.
Nur für 1, 2 und 3 Gefangene gibt es trivialerweise sichere Strategien.
MfG
Ortwin
Andreas Baus
> Nachdem alle 100 Gefangenen einmal zur Lampe gelassen wurde, muss nach
> einer endlichen Zeit einer der Gefangenen behaupten dass alle 100 bei der
> Lampe waren, unabhängig davon ob die Auswahl der Gefangenen zufällig ist
> oder ob der Wärter irgendeine Gegenstrategie entwickelt.
Naja, wenn die Gefangenen nur dann frei kommen wenn alle 100 wenigstens
einmal in dem Raum waren, dann kann ja eigentlich der Waerter fies sein und
einen der Gefangenen nie in den Raum fuehren, dann kommen die Gefangenen
nie frei, egal was sie tun...
--
----
-----------------------------------------------------------------------
[Insert joke here.] ----
--
an...@studcs.uni-sb.de (Andreas Baus)
Thomas Steffen
> Quer über den Daumen gepeilt würde ich auf ca. 35 Jahre tippen, mag
> jemand nachrechnen?
Ja, 100x100 ist zumindest die Größenordnung. Aber das reicht evtl
nicht. Der zählende Gefangene muss ja mindestens 100mal ausgesucht
worden sein. Das wäre eben jene 35 Jahre. Darüber hinaus ist es aber
insbesondere gegen Ende nicht mehr sicher, dass in der Zwischenzeit
jemand die Lampe eingeschaltet hat. Gegen Ende verlängert sich also
die Zeit geringfügig, vermutlich nur um ein paar Jahre. :-)
Andere Frage: gibt es eine wesentlich intelligentere Strategie? Dazu
müsste man wohl irgendwie Information austauschen, und zwar nicht mit
Erfolgsgarantie, aber doch unmissverständlich. Das scheint mir nicht
machbar zu sein.
--
Thomas
Ortwin Gasper
> Naja, wenn die Gefangenen nur dann frei kommen wenn alle 100 wenigstens
> einmal in dem Raum waren, dann kann ja eigentlich der Waerter fies sein und
> einen der Gefangenen nie in den Raum fuehren, dann kommen die Gefangenen
> nie frei, egal was sie tun...
Nun, das kann mit einer Wahrscheinlichkeit von 0 auch beim Zufallsprozeß
geschehen ...
MfG
Ortwin
Michael Ganser
> geschehen ...
>
Bertram Felgenhauer
[1] enthaelt eine Diskussion zu diesem Raetsel.
Die Loesungen dort gehen runter bis zu 3536 Tagen.
Die grundsaetzliche Idee bleibt die gleiche, nur mit dem
Unterschied, dass sich die Spieler darauf einigen, wann
die Lampe wievielen Zaehl-Einheiten entspricht. Damit
erreicht man, dass man in groesseren als nur Einerschritten
zaehlen kann, und letztendlich einen Zeitgewinn.
Bertram
[1] http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293
--
`.oo' "Do not meddle in the affairs of Wizards, for they
,. (`-' are subtle and quick to anger." -- J.R.R. Tolkien
'^\`-' ) "Do not meddle in the affairs of wizards, for you
c-L'- are crunchy and good with ketchup." -- Terry Pratchett
KJ Kress
> 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.
hmm .... Also das einzige was mir einfällt um 100%ig sicher zu gehen und
nicht auf die Wahrscheinlichkeiten vertrauen zu müssen, ist
einfach soviele Durchläufe abzuwarten bis wirklich jeder unter den 100 ist.
also z.b.: Lampe bleibt so lange aus bis einer ein zweites mal drinne war,
wenn man das 2te mal reinkommt dann shaltet man das Licht an (alle weiteren
ändern nix am Zustand der Lampe selbst wenn sie selber auch ein zweites mal
in den Raum kommen). Nun liegt es am Hundertsten. Wenn das Licht aus ist is
die Sache klar wenn Es an ist macht er Es aus und geht in die nächste Runde,
die diesmal nur bis 199 geht nicht bis 200, da ja bei 100 und nicht bei 101
gestartet wird. die anderen Häftlinge wissen, dass Sie in der 2ten Runde
sind, weil der Hundertste NICHT behauptet hat, dass bereits alle in dem Raum
waren. Diese Methode kann natürlich etwas dauern, da die hundert wirklich
nacheinander in den Raum müssen, ist aber zuverlässig ....
gruß
kj
Karsten Buth
Andreas Baus
Schon, aber wenn man dem Wärter völlig freie Bahn läßt (ihm erlaubt die
Gefangenen nach einer bestimmten (Gegen)Strategie auszuwählen) dann kann er
halt diese Wahrscheinlichkeit beliebig hochtreiben, trivialerweise auf 1
indem er mindestens einen Gefangenen nie aus seiner Zelle nimmt.
Deshalb müßte der Wärter eigentlich völlig unparteiisch sein (also ein
Zufallsprozeß, der nicht unbedingt gleichverteilt sein muss, aber für den
für *jeden* Gefangenen eine Wahrscheinlichkeit von >0 besteht ausgewählt zu
werden) oder der Wärter selber muß irgendwelchen einschränkenden Regeln
unterliegen die sicherstellen dass er jeden Gefangenen innerhalb einer
endlichen Zeitspanne mindestens einmal drannehmen *muß*, wenn die
Gefangenen überhaupt eine Chance haben sollen...
Marko Renner
> hmm .... Also das einzige was mir einfällt um 100%ig sicher zu gehen und
> nicht auf die Wahrscheinlichkeiten vertrauen zu müssen, ist
> einfach soviele Durchläufe abzuwarten bis wirklich jeder unter den 100 ist.
signalisieren, einer zählt.
> also z.b.: Lampe bleibt so lange aus bis einer ein zweites mal drinne war,
> wenn man das 2te mal reinkommt dann shaltet man das Licht an (alle weiteren
> ändern nix am Zustand der Lampe selbst wenn sie selber auch ein zweites mal
> in den Raum kommen).
Was hast du mit dem 2. Mal?
> Nun liegt es am Hundertsten.
Wer ist der 100. und woher weiß er, daß er es ist?
> Wenn das Licht aus ist is die Sache klar wenn Es an ist macht er Es aus und
> geht in die nächste Runde,
> die diesmal nur bis 199 geht nicht bis 200, da ja bei 100 und nicht bei 101
> gestartet wird. die anderen Häftlinge wissen, dass Sie in der 2ten Runde
> sind, weil der Hundertste NICHT behauptet hat, dass bereits alle in dem Raum
> waren. Diese Methode kann natürlich etwas dauern, da die hundert wirklich
> nacheinander in den Raum müssen, ist aber zuverlässig ....
Das verstehe ich irgendwie alles nicht...
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 anderen 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
Marco Schuler
.
Es wird ein Gefangener (G) als Zähler (Z) bestimmt.
Jeder G (außer Z) schaltet die Lampe ein, wenn er diese erstmals
ausgeschaltet vorfindet. Ist die Lampe bereits an oder hat er die Lampe
bereits einmal eingeschaltet, so lässt er den Zustand unverändert.
Z merkt sich zu Beginn die Zahl Null. Jedesmal, wenn Z eine eingeschaltete
Lampe vorfindet, schaltet er sie aus und erhöht die gemerkte Zahl um 1. Hat
er bis 99 gezählt, kann er sagen, dass alle da waren. Wie lange das ganze im
Schnitt dauert, ist mir zu kompliziert....
CU
Marco
KJ Kress
"Marco Schuler" <pand...@yahoo.de> schrieb im Newsbeitrag
news:3dc80...@news.unibw-muenchen.de...
kleine verbesserung, der zähler ist der, der am zweiten tag in den raum
geholt wird, soweit er nicht selber als erstes im raum
war kann er bereits bei 1 beginnen
gruß
kj
KJ Kress
> Das verstehe ich irgendwie alles nicht...
ich probiers nochmal ... ich wollte folgendes vorschlagen:
das licht bleibt so lange aus bis einer das zweitemal in den raum kommt, der
macht es dann an.
dann bleibt es so lange an bis der 100ste in den raum kommt bzw. der jenige
der am hundersten
tag geholt wird. der macht das licht wieder aus (da man an diesem tag nicht
entlassen wurde weiss man,
dass man in der nächsten 'runde' ist .... um das mit den runden nochmal klar
zu machen, der nächste der
in den raum kommt verhält sich als ob er noch nicht in dem raum gewesen wäre
sprich er lässt das licht
an egal wie oft er schon im raum war NUR wenn er danach nochmal geholt wird
macht er es an) und man
hofft, dass bis zum tag 199 das licht nicht wieder angemacht wurde.
dein vorschlag bzw der von marco schuler wird vermutlich nicht so lange
dauern wie meiner
(für meinen die wahrscheinlichkeit zubestimmen kann ich nicht; ich sag nur
'MUT ZUR LÜCKE :)')
allerdings besteht bei meinem vorschlag die möglichkeit bereits nach 100
tagen entlassen zu werden,
was bei eurem nicht geht ...
gruß
kj
Marko Renner
>>Das verstehe ich irgendwie alles nicht...
>
> ich probiers nochmal ... ich wollte folgendes vorschlagen:
>
> das licht bleibt so lange aus bis einer das zweitemal in den raum kommt, der
> macht es dann an. dann bleibt es so lange an bis der 100ste in den raum kommt
> bzw. der jenige der am hundersten tag geholt wird. der macht das licht
> wieder aus (da man an diesem tag nicht entlassen wurde weiss man,
> dass man in der nächsten 'runde' ist .... um das mit den runden nochmal klar
> zu machen, der nächste der in den raum kommt verhält sich als ob er noch
> nicht in dem raum gewesen wäre sprich er lässt das licht an egal wie
> oft er schon im raum war NUR wenn er danach nochmal geholt wird
> macht er es an) und man hofft, dass bis zum tag 199 das licht
> nicht wieder angemacht wurde.
Ich habe deinen Text jetzt 1,5h lang gelesen und gerätselt, was dir
diverse Informationen bringen (wenn z.B. der 21. das Licht anmacht,
weiß er, daß vorher 20 einmal drin waren) und wie man die in die
nächste Runde bringt (der 101. weiß ja schon nicht mehr, wer in der
1. RUnde wie oft drin war) bzw. welcher Gefange woher wissen soll
wann alle drin waren...
Das Ding ist zwar praktisch, wenn genau am Anfang jeder einmal gezogen
wird... und in dem Moment habe ich´s verstanden: Genau darauf
spekulierst du, und wenn es in den ersten 100 Tagen nicht geklappt hat,
schaust du eben, ob in den nächsten 100 jeder genau einmal gezogen
wird. Und das ist so unwahrscheinlich, daß ich eben nicht darauf
gekommen war, sondern in deiner Lösung krampfhaft nach einem Weg
zur Informationsübertragung bzw. zum Zählen gesucht hatte ;-)
> dein vorschlag bzw der von marco schuler wird vermutlich nicht so lange
> dauern wie meiner
Nö, keine 2,9337*10^41 Jahre ;-)
Moses
Andreas Profous
> bei dem Treffen wird ein Gefangener bestimmt, der die Lampe immer
> einschaltet, wenn er in den Raum kommt. Alle anderen schalten die Lampe
> einmal aus, wenn sie in den Raum kommen und die Lampe an ist. Wenn die
Lampe
> schon aus ist, oder sie diese schon einmal ausgeschaltet haben machen sie
> nichts.
> Der Gefangene, der die Lampe immer einschaltet muss mitzählen, wie oft er
> sie schon eingeschaltet hat und wenn er sie das 100. mal einschalten würde
> kann er sagen, dass schon alle im Raum waren. Da sie alle noch sehr jung
> sind macht es ihnen natürlich überhaupt nichts aus, ein paar Jährchen im
> Gefängnis zu verbringen.
Das verstehe ich nicht. Es könnte doch sein dass der (zugegeben
unwahrscheinliche)
Fall auftritt (angenommen Gefangener 1 ist der Auserwählte), dass z.B.
2,1,2,1,2,1,2 etc.. drankommen, beim 200. Tag würden dann alle erschossen
oder?
Andreas
Andreas Profous
> hmm .... Also das einzige was mir einfällt um 100%ig sicher zu gehen und
> nicht auf die Wahrscheinlichkeiten vertrauen zu müssen, ist
> einfach soviele Durchläufe abzuwarten bis wirklich jeder unter den 100
ist.
> also z.b.: Lampe bleibt so lange aus bis einer ein zweites mal drinne war,
> wenn man das 2te mal reinkommt dann shaltet man das Licht an (alle
weiteren
> ändern nix am Zustand der Lampe selbst wenn sie selber auch ein zweites
mal
> in den Raum kommen). Nun liegt es am Hundertsten. Wenn das Licht aus ist
is
> die Sache klar [...]
Warum ist dann die Sache klar? Es könnte doch sein dass einmal der erste
Gefangene
und dann 98mal ein anderer Gefangener in den Raum gelassen wurde (aber immer
der
gleiche) und dann wieder der erste. Dann wäre das Licht aus und alle
Gefangenen
tot, oder?
Andreas
Andreas Profous
> 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.
Ich würde sagen die Gefangenen spekulieren auf eine bestimmte Reihenfolge.
Und zwar am ersten Tag einer "Runde" der erste Gefangene, am 2. Tag der 2.
etc.
Also wenn am ersten Tag Gefangener 1 in den Raum kommt schaltet er das Licht
ein,
wenn irgendein anderer reinkommt bleibt es aus.
Wenn Gefangener 2 am 2. Tag in den Raum kommt und das Licht ist an, so lässt
er es an,
wenn ein anderer Gefangener in den Raum kommt so schaltet er das Licht aus
(oder lässt es aus).
etc.
Wenn nach 101 Tagen Gefangener 1 in den Raum kommt und das Licht ist an, so
behauptet er
alle seien dringewesen, ansonsten beginnt das Spiel von vorne.
Dauert leider etwas lange das Ganze... :)
Andreas
KJ Kress
> Warum ist dann die Sache klar? Es könnte doch sein dass einmal der erste
> Gefangene
> und dann 98mal ein anderer Gefangener in den Raum gelassen wurde (aber
immer
> der
> gleiche) und dann wieder der erste. Dann wäre das Licht aus und alle
> Gefangenen
> tot, oder?
nein, hast mich falsch verstanden .... nur wenn du genau das zweite mal
reinkommst machst du das licht an danach lässt du es an
aber ich hab nochmal etwas klarer probiert zu erklären was ich meinte ...
par postings früher
gruß
kj
Andreas Profous
> reinkommst machst du das licht an danach lässt du es an
> aber ich hab nochmal etwas klarer probiert zu erklären was ich meinte ...
> par postings früher
Ah ich verstehe, das Licht ist quasi der Anzeiger ob in der aktuellen Runde
mindestens einer mindestens 2mal im Raum war. Ich denke das funktioniert :)
Ist auch ungleich schneller als meine Methode weil es bei dir egal ist in
welcher
Reihenfolge die Gefangenen drankommen.
Wenn ich mich nicht täusche ist die Wahrscheinlichkeit in einer Runde zum
Erfolg zu kommen (dass kein Gefangener doppelt reinkommt)
100!/(100^100) oder ca. 9.33*10^(-43), also dauert es durchschnittlich
2.93*10^41 Jahre freizukommen....
Ciao
Andreas
Andreas Baus
Der Schlüssel ist
"Wenn die Lampe schon aus ist, ODER SIE DIESE SCHON EINMAL AUSGESCHALTET
HABEN machen sie nichts"
Also, angenommen 1 ist der 'Zähler', und die Lampe ist am anfang aus, dann
tut 2 nichts wenn er zum ersten mal in den Raum kommt; dann kommt 1 und
schaltet sie ein, 2 findet sie brennend vor und schaltet sie aus (da es
sein erstes mal ist), 1 schaltet sie wieder ein, und danach passiert nichts
mehr, da 2 sie j schon einmal ausgeschaltet hat. 1 weiss also, da er die
lampe erst einmal eingeschaltet hat, dass erst ein anderer Gefangener in
dem Raum war; und nur mit jedem neuen, der vorher noch nicht drin war, wird
die Lampe wieder ausgeschaltet und signalisiert damit dem Zähler dass er um
eins weiterzählen kann...
Andreas Profous
> "Wenn die Lampe schon aus ist, ODER SIE DIESE SCHON EINMAL AUSGESCHALTET
> HABEN machen sie nichts"
Alles Klar der Groschen ist gefallen :)