Gefangenrätsel--Zusatz
KJ Kress
noch nicht überzeugt hatte die beste zu sein.
Für alle die sich nicht daran erinnern oder die die es nicht kennen:
100 Gefangene werden zu Lebenslänglicher Haft verurteilt. Sie erahlten
allerdings eine Möglichkeit diese Strafe zu mindern.
Die 100 Gefangenen werden in 100 einzel Zellen untergebracht von denen aus
keine Möglichkeit besteht mit einem Mithäftling zu kommunizieren. Weiterhin
teilt der Wächter den Gefangenen mit, dass jeden Tag einer von Ihnen (per
Zufall) ausgewählt wird der in einen Raum mit einer Lampe und deren Schalter
geführt wird, dort darf er den Schalter betätigen. Während dieser Prozedur
besteht ebenfalls keine möglichkeit zur Kommunikation.
Sobald einer der Gefangenen dem Wächter sagt, dass bereits jeder Häftling
mindestens einmal in diesem Raum war und es stimmt, dann werden alle
entlassen, wenn es aber einer der Gefangenen behauptet und es nicht stimmt,
dann werden sofort alle erschossen!
Welches ist die beste Gewinnstrategie für die Gefangenen?
Alle werden natürlich unendlich alt und sind gleich schlau :)
Achja die Häftlinge haben natürlich _bevor_ sie weggesperrt werden die
Möglichkeit sich abzusprechen!
So ich wollte einen Lösungszusatz vorschlagen, der meiner Meinung nach das
ganze deutlich beschleunigt, aber ich lasse mich durch ein Nachrechnen auch
gerne belehren :))
Spoiler für die die Aufgabe nicht kennen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
So.....
Wenn ich mich recht erinnere war der letzte Stand der Dinge:
Es wird ein Zähler bestimmt der das Licht sobald er rankommt ausmacht und
einen weiter zählt, und nur diejenigen das Licht anmachen die nocht nicht
gezählt wurden.
So hierbei sollte man vermutlich am besten den 2ten der in den Raum geholt
wird zum Zähler machen, da er ja bereits bei 2 beginnen kann zu zählen. Wenn
zweimal der selbe geholt wird zu beginn ist er ebenfalls der Zähler, jedoch
bei 1 beginnend.
So ich denke es ist vermutlich besser, dass derjenige Zähler wird der als
_erstes_ das _zweitemal_ in den Raum geholt wird. So um dass nochmal
durchzuspielen:
Diejenigen die geholt werden, lassen die Lampe aus, und derjenige der als
erstes zum zweiten mal geholt wird schaltet es an um den nachfolgenden zu
zeigen, dass sie NICHT der Zähler sind (wenn sie zum 2tenmal geholt werden)!
Das Problem nun ist zu unterscheiden zwischen einer normalen wertungsrunde
(wie oben) und der Zählersuchrunde. Ist aber auch nicht so wild, da die
Zählersuchrunde ja maximal 100 Tage dauert. Demnach beginnt derjenige der am
101rsten Tag geholt wird die WErtungsrunde, es sei denn er wurde bereits
gewertet, das weiss man daher ob man in den Raum kam mit brennendem Licht
oder gelöschten, alle die das Licht aus vorfinden werden automatisch
gewertet. Achja der 101rste löscht in JEDEM Fall das Licht, es sei denn er
will sich werten lassen.
wenn der 101rste eine gelöschte Lampe vorfindet könnte er sofort verkünden,
dass bereits alle im Raum waren.
So ... ich hoffe ich hab mich nicht allzu unklar ausgedrückt, un ihr
erinnert euch an die Lösung aus der Originallösung :))
Aber ich denke dieser Zusatz sollte das ganze deutlich beschleunigen
gruß
KJ
--
Etwas nicht zu können ist kein Grund es nicht zu tun!
Sabine Kläring
"KJ Kress" <hitz...@gmx.de> schrieb im Newsbeitrag news:bcjru6$aqh$1...@nets3.rz.RWTH-Aachen.DE...
> Vor ein paar Monaten hatten wir mal ein Gefangenenrätsel, dessen lösung mich
Sorry, ich habe keine Lösung,
und komme auch mit deinem Lösungsvorschlag nicht recht klar.
(Bin ich zu doof?)
Magst du (oder jemand anderes) vielleicht kurz skizzieren, wie z.B.
5 Gefangene dieses Problem lösen können?
Ggf. kannst du es aussagekräftig sogar mit noch weniger
Leuten demonstrieren.
(schon bei 3en bekomme ich Probleme. Mutig, so ein Selbstbekenntnis?)
Magst du?
Sabine
Sebastian Stigler
news:bcjru6$aqh$1...@nets3.rz.RWTH-Aachen.DE:
>
> Wenn ich mich recht erinnere war der letzte Stand der Dinge:
> Es wird ein Zähler bestimmt der das Licht sobald er rankommt
> ausmacht und einen weiter zählt, und nur diejenigen das Licht
> anmachen die nocht nicht gezählt wurden.
> So hierbei sollte man vermutlich am besten den 2ten der in den
> Raum geholt wird zum Zähler machen, da er ja bereits bei 2
> beginnen kann zu zählen. Wenn zweimal der selbe geholt wird zu
> beginn ist er ebenfalls der Zähler, jedoch bei 1 beginnend.
So und jetz noch ne kleine Mathematikerklugscheißeranmerkung:
Die vorgeschlagene Lösungen (sowohl deine als auch die
Ursprüngliche) kann aber dennoch zu einem Fehler führen, da ihr
alle angenommen habt, dass die Gefangenen die Möglichkeit haben die
Tage zu zählen. Das muß aber nicht so sein, den sie könnten in
Zellen ohne Fenster eingesperrt werde, zu unregelmäßigen Zeiten ihr
Essen bekommen und zu unregelmäßigen Zeiten in die Zelle mit der
Lampe geführt werden.
In der Aufgabenstellung ist aber nur gesagt, das pro Tag je ein
Gefangener ein diese Zelle geführt wird, was dazu führt, das
bestenfalls nur dieser Gefangene weiß, dass ein Tag vergangen ist.
Für die anderen Gefangen ist es nicht im geringsten sicher, das
schon eine feste Zahl von Tagen vergangen ist, da diese keine
Möglichkeit haben regelmäßige Ereignisse (Tag/Nacht, feste
Essenszeiten o.ä. (Es ist Experimentell erwießen, das Menschen, die
keine solchen Trigger erhalten, ihr Zeitgefühl verlieren)) zu
zählen. Demnach ist eine sichere Aussage erst nach 100
Wertungsschleifen möglich.
Mfg Sebastian
Andreas Riedel
> So und jetz noch ne kleine Mathematikerklugscheißeranmerkung:
> Die vorgeschlagene Lösungen (sowohl deine als auch die
> Ursprüngliche) kann aber dennoch zu einem Fehler führen, da ihr
> alle angenommen habt, dass die Gefangenen die Möglichkeit haben die
> Tage zu zählen.
Davon würde ich aber schon ausgehen. Wenn etwas in der Aufgabenstellung
nicht erwähnt wird, nimmt man es ja als "ganz normal" an.
> (Es ist Experimentell erwießen, das Menschen, die
> keine solchen Trigger erhalten, ihr Zeitgefühl verlieren))
Bei Hühnern wird das sogar praktisch genutzt: Die legen täglich ein Ei,
auch wenn man die "Tage" durch künstliche Beleuchtung etwas kürzer
macht. Deshalb sind die KIM-Eier auch meist kleiner als die vom Bauern.
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)
KJ Kress
Unter Vorraussetzung, dass die Gefangenen die Tage zählen können!
also 5 Gefangene mit der Ursprungsvariante:
Der Gefange der am zweiten Tag den Raum mit dem Lichtschalter betritt ist
der Zähler.
Tag1: Gefangener 3 wird geholt.
Tag2: G1 wird geholt --> G1 = Zähler (Er zählt sich und den Vorgänger also
2)
Tag3: G3 wird erneut geholt er lässt das Licht aus, da er schon gewertet
wurde
Tag4: G2 wird geholt -> Er macht das Licht an, da er noch nicht gewertet
wurde
Tag5: G1 wird gehilt -> Er macht das Licht aus und Zählt +1 also 3
Tag6: G1 wird geholt passiert nix
Tag7: G2 wird geholt passiert auch nix
Tag8: G4 wird geholt -> er macht das Licht an weil er noch nicht gewertet
wurde
Tag9: G5 wird geholt -> Er lässt die Lampe wie sie ist, da er die WErtung
nicht durcheinander bringen will
Tag10: G1 wird geholt -> Er macht die Lampe aus und wertet +1 also 4
Tag11: G5 wird geholt -> macht das Licht an, da er ja noch nicht gewertet
wurde.
Tag12: G1 wird geholt -> Wertet +1 also 5 und verkündet , dass mittlerweile
alle in dem Raum waren!
Meine Änderung : Derjenige, der als erstes das 2te mal geholt wird wird
Zähler:
Tag1: G1 - Licht aus
Tag2: G3 - Licht aus
Tag3: G4 - Licht aus
Tag4: G1 - Licht an (um den nachfolgende klarzumachen, dass er Zähler ist
und 2mal im Raum war) zählt die Tage -1 also 3
Tag5: G5 - Licht an
Tag6: G2 - Licht an - weil jetzt die zweite Runde bginnt und ab jetzt wie
oben gewertet wird, da er das Licht brennend vorfindet, weiß er daß
mindestens einer doppelt in dem Raum war und somit weiter gewertet werden
muss.
Tag7: G1 - Licht aus - Wertung+1 -> 4
Tag8: G3 - macht nix weil schon gewertet wurde
Tag9: G5 - Licht an
Tag10: G1 - licht aus - Wertung+1 -> 5 -> verkündet, dass alle drinne waren
Der Vorteil der zweiten Variante kommt nicht so gut raus, aber umso mehr
Gefangene, desto vorteilhasfter kann diese sein!
gruß
KJ
Alfred Heiligenbrunner
>
> Der Vorteil der zweiten Variante kommt nicht so gut raus, aber umso mehr
> Gefangene, desto vorteilhasfter kann diese sein!
Im Mittel dauert es - wenn ich mich nicht verrechnet habe - 13.21 Tage,
bis von den 100 Gefangenen einer zum zweiten Mal ausgewählt wird.
(Gleichverteilung vorausgesetzt.)
In den ersten 100 Tagen zählst Du mit Deiner Methode daher im Mittel 12.
21 Gefangene.
Bei der Methode "Gefangener vom 2. Tag ist Zähler" werden in den ersten
100 Tagen dagegen nur etwa 3 Gefangene gezählt, weil es im Mittel ja 100
Tage dauert, bis der Zähler wieder ausgewählt wird.
Ab dem 101. Tag funktionieren beide Methoden ja wieder gleich.
Noch ein kurzer Versuch, die Methode von KJ Kress und die
Standardmethode zu erklären.
Prinzipiell dient das Licht als Informationsträger. Dieses 1 Bit
Information sagt dem aktuellen Gefangenen, ob er sich selbst jetzt zum
Zählen anmelden darf. Und dem Zähler sagt es, dass er die Anzahl, die er
sich gemerkt hat, wieder erhöhen kann.
Die Standardlösung sieht vor, dass IM VORHINEIN ein Gefangener als
Zähler bestimmt wird.
Jeder Gefangene hat die Aufgabe, 1 Mal den Lichtschalter von "aus" auf
"ein" umzuschalten. Dann wird er gezählt und braucht bzw. darf nichts
weiter mehr tun.
Jedesmal wenn zufällig der Zähler in die Kammer mit der Glühbirne
geführt wird, erkennt er am Licht, ob während seiner Abwesenheit ein
noch nicht gezählter Gefangener in der Kammer war.
Er verlässt die Kammer in jedem Fall mit ausgeschaltetem Licht.
Der Zähler wartet, bis er 99 Mal eine eingeschaltete Glühbirne
vorgefunden hat und kann dann verkünden, dass jetzt alle Gefangenen
mindestens einmal in der Kammer waren.
Anders die Lösung von KJ Kress:
Während der ersten 100 Tage dient das Licht als Kennzeichen, ob schon
jemand zum 2. Mal in der Kammer war. Am Anfang ist das Licht ausgeschaltet.
Jeder der das Licht weiterhin ausgeschaltet vorfindet, läßt es
ausgeschaltet und kann sich als gezählt betrachten. Der erste, der zum
2. Mal in die Kammer kommt, schaltet das Licht ein und signalisiert so
seinen Mitgefangenen, dass
1) ein Zähler gefunden ist, und
2) die weiteren "Besucher" der Kammer bis zum 100. Tag nicht mehr
gezählt werden. (Man weiß ja nicht, wieviele von ihnen doppelt und
mehrfach hineinkommen!)
Erst am 101. Tag wechseln die Gefangenen wieder auf die Strategie aus
der Standardlösung (s.o.).
Voraussetzung ist unter anderem natürlich, dass sich jeder der
Gefangenen gleich gut als Zähler eignet.
Ich hoffe, etwas mehr Licht in die Angelegenheit gebracht zu haben. :-)
MfG
Alfred
>
> gruß
>
> KJ
>
KJ Kress
>
> Ich hoffe, etwas mehr Licht in die Angelegenheit gebracht zu haben. :-)
hehe... jupp genauso meinte ichs :) thx
KJ
Alfred Heiligenbrunner
> Die Standardlösung sieht vor, dass IM VORHINEIN ein Gefangener als
> Zähler bestimmt wird.
Noch eine Anmerkung.
Die Standardlösung dauert im Mittel 10417.73 Tage = 28.52 Jahre.
Die Lösung von KJ Kress dauert im Mittel 9384.53 Tage = 25.69 Jahre.
Dass die Ersparnis nicht größer ist, liegt daran, dass das zeitintensive
"Warten auf die Letzten" sich auch in der Kress-Lösung niederschlägt.
Ich hoffe, mich nicht verrechnet zu haben. Kombinatorikprobleme sind
immer sehr fehleranfällig.
MfG
Alfred
KJ Kress
> Noch eine Anmerkung.
> Die Standardlösung dauert im Mittel 10417.73 Tage = 28.52 Jahre.
> Die Lösung von KJ Kress dauert im Mittel 9384.53 Tage = 25.69 Jahre.
naja immerhin knapp 3Jahre :))
Klaus Müller
ich glaube, da kann was nicht stimmen:
"KJ Kress" <hitz...@gmx.de> schrieb
> Meine Änderung : Derjenige, der als erstes das 2te mal geholt wird wird
> Zähler:
>
> Tag1: G1 - Licht aus
> Tag2: G3 - Licht aus
> Tag3: G4 - Licht aus
> Tag4: G1 - Licht an (um den nachfolgende klarzumachen, dass er Zähler ist
> und 2mal im Raum war) zählt die Tage -1 also 3
> Tag5: G5 - Licht an
> Tag6: G2 - Licht an - weil jetzt die zweite Runde bginnt und ab jetzt wie
> oben gewertet wird, da er das Licht brennend vorfindet, weiß er daß
> mindestens einer doppelt in dem Raum war und somit weiter gewertet werden
> muss.
> Tag7: G1 - Licht aus - Wertung+1 -> 4
> Tag8: G3 - macht nix weil schon gewertet wurde
Woher weiss jetzt G3, dass er nichts machen soll? Er ist das 2. Mal im Raum
und das Licht ist aus.
Irgendwie wird mit Deiner Methode das eine zur Verfuegung stehende Bit
mehrfach benutzt. Einmal zum Zaehlen, aber auch um die Information zu
uebertragen, wer der Zaehler sein soll. Das sollte eigentlich gar nicht
funktionieren koennen.
Oder hab' ich da jetzt was ganz dummes uebersehen?
Gruss Klaus.
KJ Kress
> > Tag1: G1 - Licht aus
> > Tag2: G3 - Licht aus
> > Tag3: G4 - Licht aus
> > Tag4: G1 - Licht an (um den nachfolgende klarzumachen, dass er Zähler
ist
> > und 2mal im Raum war) zählt die Tage -1 also 3
> > Tag5: G5 - Licht an
> > Tag6: G2 - Licht an - weil jetzt die zweite Runde bginnt und ab jetzt
wie
> > oben gewertet wird, da er das Licht brennend vorfindet, weiß er daß
> > mindestens einer doppelt in dem Raum war und somit weiter gewertet
werden
> > muss.
> > Tag7: G1 - Licht aus - Wertung+1 -> 4
> > Tag8: G3 - macht nix weil schon gewertet wurde
>
> Woher weiss jetzt G3, dass er nichts machen soll? Er ist das 2. Mal im
Raum
> und das Licht ist aus.
> Irgendwie wird mit Deiner Methode das eine zur Verfuegung stehende Bit
> mehrfach benutzt. Einmal zum Zaehlen, aber auch um die Information zu
> uebertragen, wer der Zaehler sein soll. Das sollte eigentlich gar nicht
> funktionieren koennen.
> Oder hab' ich da jetzt was ganz dummes uebersehen?
Ich drücke mich bei solchen Erklärungen meist relativ kompliziert aus, es
wurde aber schon besser formuliert von ' xx ' weiss nicht mehr weil mein
Outlxxx das nicht mehr anzeigt ;( keine ahnung wie ich das änder.
Ich probiers aber nochmal :)
Also In der _ersten_ Runde wird das Bit benutzt um festzulegen wer der
Zähler seien wird, sobald dieser feststeht, signalisiert er dies indem er
das Licht anschaltet, daher wissen alle nachfolgenden in dieser Runde, dass
sie _nicht_ gezählt werden, da diese Runde ja nur der Zählerfindung dient.
mit Runde mein ich übrigens die dauer der Anzhal Gefangener (also 77
Gefangene -> 1 Runde = 77 Tage)
Ab der zweiten Runde läuft das ganze wie gehabt ab, nur dass der Zähler bei
einer höheren Zahl beginnt. wenn der erste der zweiten Runde ein nicht
brennendes Licht vorfindet weiss er, dass es noch keinen Zähler gibt und
daraus folgt, dass jeder in dem Raum schon gewesen sein muss. Ab der zweiten
Runde wird das Bit wie gehabt benutzt.
ich hoffe das war verständlicher :)
gruß
KJ
Niko
Denselben Fehler seh ich auch.
Zwar ist am 8. Tag der Zähler definitiv schon gefunden (denn spätestens nach
dem 5. Tag muß jemand schon 2mal drin gewesen sein). Umgemünzt auf die
Groß-Aufgabe heißt das aber, daß man die vollen 100 Tage warten muß, um zu
erkennen ob das Licht nun aus ist weil noch niemand "Zähler" spielt oder
weil eben gerade so gezählt wird. Und nach 100 Tagen wäre jeder Vorteil weg.
Falls ich falsch liege freuts mich, denn der Ansatz war echt gut.
Gruß Nick
Jan Darmochwal
> Umgemünzt auf die
> Groß-Aufgabe heißt das aber, daß man die vollen 100 Tage warten muß, um zu
> erkennen ob das Licht nun aus ist weil noch niemand "Zähler" spielt oder
> weil eben gerade so gezählt wird. Und nach 100 Tagen wäre jeder Vorteil weg.
Neulich hat hier jamand ausgerechnet, dass es nach der
"Standardmethode" im Durchschnitt über 28 Jahre dauert, bis die
Gefangenen draußen sind, die 100 Tage fallen also kaum ins Gewicht.