100 Gefangene

Freizeit & Hobby Rätsel
#1

Also erst mal hallo an alle, hoffe wir haben viel spaß miteinander und können einander in zukunft helfen

Nun zum Rätsel:

100 Gefangene haben die Chance frei zu kommen. Alle 100 kommen in einen gemeinsamen Raum für 10 minuten. Dort dürfen sie miteinander reden. Nach diesen 10 minuten kommen sie alle in Einzelhaft. Keiner kann den anderen sehen oder hören. Jeden Tag wird einer der Gefangenen zufällig ausgewählt(völlig zufällig also kann ein Gefangener auch mehrmals in den Raum kommen bevor jeder andere drin war) und kommt in einen Raum in dem nur eine Lampe und der dazugehörige Schalter, mit dem man die Lampe nur ein- und ausschalten kann(also nur zwei Zustände), ist. Der Gefangene kann den Zustand der Lampe ändern oder nicht und kommt danach sofort wieder in Einzelhaft.
Jeder Gefangene kann zu einem beliebigen Zeitpunkt sagen das bereits alle mindestens einmal in dem raum mit der lampe waren. Jedoch darf das nur einmal ein Gefangener machen und danach nie wieder einer, auch kein anderer. Hat der Gefangene recht sind sie alle frei.

Was müssen die Gefangenen sich ausmachen um noch bei lebzeiten raus zu kommen?(Die schnellste Variante ist immer die beste)

mfg

Michael

#2

UI, da muss man ja wirklich nachdenken (Lösung?)
Hi,

Nun zum Rätsel:

100 Gefangene haben die Chance frei zu kommen. Alle 100 kommen
in einen gemeinsamen Raum für 10 minuten. Dort dürfen sie
miteinander reden. Nach diesen 10 minuten kommen sie alle in
Einzelhaft. Keiner kann den anderen sehen oder hören. Jeden
Tag wird einer der Gefangenen zufällig ausgewählt(völlig
zufällig also kann ein Gefangener auch mehrmals in den Raum
kommen bevor jeder andere drin war) und kommt in einen Raum in
dem nur eine Lampe und der dazugehörige Schalter, mit dem man
die Lampe nur ein- und ausschalten kann(also nur zwei
Zustände), ist. Der Gefangene kann den Zustand der Lampe
ändern oder nicht und kommt danach sofort wieder in
Einzelhaft.
Jeder Gefangene kann zu einem beliebigen Zeitpunkt sagen das
bereits alle mindestens einmal in dem raum mit der lampe
waren. Jedoch darf das nur einmal ein Gefangener machen und
danach nie wieder einer, auch kein anderer. Hat der Gefangene
recht sind sie alle frei.

Was müssen die Gefangenen sich ausmachen um noch bei lebzeiten
raus zu kommen?(Die schnellste Variante ist immer die beste)

Also ob das die schnellste Variante ist, weiß ich nicht, aber die Gefangenen müssen sich zuerst mal selbst fortlaufende Nummern zwischen 1 und 100 geben und die Tage mitzählen, die sie bereits in Gefangenschaft sind. Diese Tage teilen sie untereinander auf. Der Gefangene 1 ist zuständig für die Tage 1, 101, 201, 301 usw.
der Gefangene 38 ist zuständig für die Tage 38, 138, 238, 338 usw.,
usf.

wird ein Gefangener an einem Tag verhört, für den er nicht zuständig ist, knippst er das Licht aus und signalisiert seinem Nachfolger damit, dass er keine sinnvolle Schlußfolgerung aus dem letzten Verhör ziehen darf. Wird ein Gefangener an einem Tag verhört, für den er zuständig ist, dann tut er folgendes:

Ist es der Gefangene 1, dann schaltet er das Licht ein, womit sein Nachfolger weiß, dass der Gefangene 1 bereits verhört wurde. Handelt es sich um einen anderen Gefangenen i ( 2 - 100 ), dann schaltet er das Licht ein, wenn das Licht bereits eingeschaltet war, als er den Verhörraum betrat oder falls er das Licht bereits bei einem früheren Verhör einmal eingeschaltet hatte (damit weiß der nachfolgende Verhörte, dass ALLE Gefangenen von 1 bis i bereits verhört wurden) andernfalls schaltet er das Licht aus.

Sobald der Gefangene mit der Nummer 100 den Verhörraum betritt und die Zahl der Tage der Gefangenschaft durch 100 teilbar ist und das Licht eingeschaltet ist, kann er sicher sagen, dass alle Gefangenen verhört wurden.

Nach meiner Schätzung müssen die Gefangenen aber wahrscheinlich trotzdem viele Jahre warten, bis sie freikommen.
Hat jemand vielleicht eine bessere (schnellere) Idee?

ciao

unimportant

#3

Einfache (langsame) Lösung

Hallo,

So müsste es im Prinzip gehen:

Die Gefangen wählen aus ihrer Mitte einen „Zaehler“, die restlichen 99 bleiben „Normalos“. Dann läuft es so ab:

Der 1., der am 1. Tag den Raum betritt schaltet das Licht ein (falls es das nicht schon ist).

Jeder Normalo, der irgendwann den raum betritt und ERSTMALIG das Licht ausgeschaltet vorfindet, schaltet es ein.

Kein Normalo schaltet je das Licht 2x ein.

Kein Normalo schaltet je das Licht aus.

Der zaehler schaltet das Licht aus, wann immer er es eingeschaltet vorfindet und zählt um eins hoch. Hat er bis 99 gezählt, beendet er das Spiel.

Nachteil: Da der Zähler im Schnitt nur alle 100 Tage 1x den Raum betritt, dauert das Spiel im günstigsten Fall ca. 100x100 Tage. Ich habe schon eine schnellere Variante gefunden (die mit mehreren Zählern funktioniert), aber die ist etwas langwierig zu becshreiben.

Viele Grüsse erstmal, Walkuerax

#4

Ich hoff doch das man da nachdenken muss! Ich hab ein echt schweres Rätsel aus meiner Sammlung ausgesucht um mal zu schaun welche Genies hier so rumhängen.

Versteh ich deine Lösung nicht ganz richtig oder meinst du das echt so:

Man stelle sich mal vor der Gefangene 1 kommt gleich am ersten Tag zur Lampe und schaltet ein. Am nächsten Tag kommt der Gefangene 40 rein schaltet das Licht aus. Jetzt müssen alle Gefangenen warten bis Gefangener 1 wieder reinkommt(am richtigen Tag!) und es einschaltet, wobei der einzige Nachfolgen der Gefangene 2 sein darf, sonst wird das Licht ja wieder ausgeschaltet.

Die Wahrscheinlichkeit das genau die richtigen zwei hintereinander reinkommen ist 1/10000. Man bedenke aber noch sie dürfen nicht irgendwann hintereinander reinkommen sondern am richtigen Tag. Die Wahrscheinlichkeit am richtigen Tag reinzukommen ist schon für einen Gefangenen 1/10000. Jetzt müssen es aber mindestens zwei sein sonst geht ja nix weiter von der Zählung her also (1/10000)^2, wobei das Spielchen ja 100 mal durchlaufen werden muss da es ja 100 Gefangene sind. (Das das für die ersten beiden Personen mal zutrifft dauert das ja schon Jahre)

Hab ich das wirklich richtig verstanden? Wenn ja sag ich nur „Lebenslänglich“.

mfg

Michael

#5

Vollkommen richtig die Lösung!

Das mit der Länge stimmt aber nicht. Im günstigsten Fall sind sie in 198 Tagen draußen(Der Zähler kommt an jedem geraden Tag rein und kein Gefangener kommt zweimal rein)

Die Lösung mit mehreren Zählern würd mich aber sehr interessieren.

Wennst so nett wärst schreibs bitte auf, würd gern wissen wie die gehn soll.

mfg

Michael

#6

Au, ich seh, dass Du recht hast,

obwohl der 10., wenn er erst einmal an einem seiner Tage das Licht angeschaltet hat, ab dann immer das Licht anschaltet, wenn es sein Tag ist, auch wenn nicht der 9. unmittelbar vor ihm beim Verhör war, dauert das immer noch viel zu lange.

Ich schlage daher folgende Modifikation vor. Wenn der Gefangene i an einem Tag k*100 + j verhört wird, welcher nicht zu ‚seinen‘ Tagen zählt, also z.B. Gefangener Nr. 8 wird am Tag 547 verhört und er dabei das Licht eingeschaltet vorfindet, dann merkt er sich das (genau merkt er sich immer aktuell das maximale j, bei dem dies der Fall war) und ab diesem Zeitpunkt, wird er jedesmal das Licht einschalten, wenn er an einem Tag h*100+m wobei m=j schaltet er das Licht wieder aus. Wenn dies alle Gefangenen tun müsste sich die Zeit sehr drastisch verkürzen.

grüße

unimportant

#7

Vermutlich schnellere (optimierbare) Lösung
Hallo,

Das mit der Länge stimmt aber nicht. Im günstigsten Fall sind
sie in 198 Tagen draußen(Der Zähler kommt an jedem geraden Tag
rein und kein Gefangener kommt zweimal rein)

Du hast recht, ich meinte auch nicht, die allergünstigste Lösung, sondern: wenn im Schnitt wirklich jeder alle 100 Tage drankommt, dann werden es so grob 10000 Tage. Wenn es sehr ungleich verteilt ist (z.B. ausgerechnet der Zähler nur alle 1000 Tage drankommt) dann kann es beliebig lang werden.

Ich bin mir nicht ganz sicher, denke aber, man kann es abkürzen, wenn man am Anfang mehrere Zähler bestimmt, sagen wir 10.

  1. Die Anfangsphase läuft wie gehabt, aber jeder der 10 Zähler darf das Licht ausschalten und um eins hochzählen. Jeder Zähler zählt nur bis 10 (sich selbst eingerechnet). Dies geht erstmal wesentlich schneller. Jeder Zähler, der seine 10 voll hat, hört auf (schaltet das Licht nicht mehr aus.) Wenn alle Zähler bei 10 angelangt sind, müssen sie sich dies kommunizieren und das Spiel beenden. (Was leicht gesagt ist und etwas schwieriger getan.)

  2. Damit die Zähler merken könne, wann sie alle fertig sind, wird ein Superzähler bestimmt, sowie eine Zeitspanne, die zur Kommunikation unter den Zählern bestimmt ist. Sagen wir, der 2001. bis 2100. Tag ist zur Kommunikation unter den Zählern vorgesehen. In dieser Zeit schalten die Normalos gar nicht. (Ausser, dass am 2001. Tag das Licht ausgeschaltet wird).

In dieser Phase schaltet jeder Zähler, der schon fertig ist, das Licht ein (wie vorher: jeder nur 1x). Der Superzähler schaltet das Licht aus und zählt um eins hoch. Wenn er bei 10 angelangt ist (sich selbst eingeschlossen) beendet er das Spiel.

Sind noch nicht alle Zähler fertig, war die Zeitspanne ab 2001. Tag zu kurz gewählt (Pech!).

Sind alle Zähler schon fertig, aber der Superzähler findet in den 100 Tagen nicht alle, dann ist die Spanne von 100 Tagen zu kurz gewählt (Pech!).

Beides macht aber höchstens 100 Tage Nachteil gegenüber Variante (1) und
läßt sich vermutlich optimieren, wenn man genug Zeit dazu hat.

  1. Führt die 2. Etappe nicht zum Ziel, wird ab dem 2101. Tag da weitergemacht wo am 2000. aufgehört wurde. (In diesem Fall hat man aber zur Variante (1) höchstens 100 Tage Nachteil und die sollten es wert sein.)

  2. Es gibt 1 Anschlussproblem: Da am 2001. Tag das Licht ausgeschaltet wird, geht - sofern es denn eingeschaltet war - die Information eines Normalos verloren. Derjenige, der das Licht an diesem Tag ausschaltet muss dies im Blick behalten (er weiß, dass die nächsten 100 Tage in den Sand gesetzt sind, denn wenn das Licht an ist, können noch nicht alle Zähler durch sein) und die Information ab Punkt 3 weitergeben, sprich das Licht 1x zusätzlich einschalten.

Müsste meiner Meinung nach auf keinen Teil Nachteile gegenüber Variante (1) bringen und in den meisten Fällen Vorteile.

Mit vielen Grüssen, Walkuerax

#8

was, wenn das licht ganz am anfang schon an ist und der zähler kommt als erster in den raum? dann zählt er einen zuviel.
jeder muß das licht genau 2x anschalten, wenn der zähler dann bei 200 angelangt ist kann er sicher sein, daß alle mindestens 1x den raum betreten haben, alle außer einer sogar mindestens 2x.

#9

Noch einfacher
Also mir sind alle vorgeschlagenen Lösungen zu kompliziert:

Meine Gefangenen vereinbaren, an einer bestimmten Stelle im Raum einen Strich zu machen. Und zwar jeder dann, wenn er erstmals den Raum betritt, dann nicht mehr. Der Strich kann mit Stift sein, sollte ein Gefangener so etwas besitzen, eingeritzt mit dem Fingernagel oder meinetwegen mit Blut. (Was tut man nicht alles, um bald frei zu kommen!)
Damit die Striche schnell zu überblicken sind, müssen sie anschaulich dargestellt werden: Jeder fünfte stricht die vier bisherigen durch, wie das eben so üblich ist.
Wenn der Hundertste an der Reihe wäre, dann weiss er Bescheid.

Einwand: Und wenn von Seiten der Wärter daran manipuliert wird?
Dieser Einwand macht aber auch alle bisherigen Lösungen hinfällig.
Das mit einer Glühbirne ist mir zu unsicher - wer weiss, ob das nicht ein Billigprodukt ist, das nach 100 Stunden für immer ausgeht!

Bernhard

#10

Genau wegen solchen Lösungen hab ich geschrieben das sie nur den Zustand der Lampe ändern können und sofort wieder rauskommen.

mfg

Michael

#11

Es gibt leider einen Gedankenfehler in deiner Lösung:

In den Tagen 2001-2100 müssten alle 10 Zähler reinkommen und dazwischen der Superzähler. Das passiert aber so gut wie nie also kommt der Superzähler nie auf 10 und sie machen ewig lang weiter.

mfg

Michael

#12

Der Zähler weiß dann ja das er der erste ist und zählt nicht außerdem ist das licht sowieso zu beginn aus.

mfg

Michael

#13

Nö
Hallo,

Das ist kein Fehler, nur sind die Zeiten noch nicht optimiert.
Du hast schon recht, die 100 Tage sind zuwenig. Es müssten ca. 1000 Tage im 1. und 1000 Tage im 2. Schritt sein. Dann wäre man immerhin im Mittel schon nach 2000 Tagen fertig (im Vergleich zu 10000 Tagen, falls man nur einen Zähler bestimmt).

Aber auch, wenn man nicht optimiert, würde man nicht ewig weitermachen, denn die schon gezählten Werte gingen nicht verloren. Man müsste einfach abwechselnd die Zeitfenster für die Zählung der Normalos und für die Zählung der Zähler verabreden und jedesmal da weitermachen, wo man das Mal davor aufgehört hat.

Der einzige Nachteil den ich sehe ist, dann man nicht die ultrakurze Lösung von 298 Tagen erreichen könnte, aber die ist sowieso so unwahrscheinlich, dass ich im echten Fall lieber eine Lösung mit kurzer mittlerer Zeit vorziehen würde.

Mit vielen Grüssen, Walkuerax

#14

Lösung ganz falsch
Ich bin jetzt auf was draufgekommen das die Lösung in der Form nicht zulässt:

sagen wir am Tag 1995 kommt der Gefangene 40 zum ersten Mal rein und schaltet das licht ein. Jetzt kommt aber bis zum Tag 2000 kein zähler rein und dann beginnt die Zähl-Phase für die Zähler und das eine Licht des Gefangenen 40 is weg aber er schaltet nie wieder das Licht ein also is die Info für immer weg.

mfg

Michael

#15

Nein
Hallo,

Nein, das habe ich berücksicht. Dies ist mein „Anschlussproblem“, was ich als Punkt 3. in meiner komplizierteren Lösung gepostet habe. (Diese Information muss von dem aufgenommen und weitergeleitet werden, der am 2001. Tag das Licht ausschaltet.)

Mit vielen Grüssen, Walkuerax

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#16

stimmt sry

aber das haltet trotzdem wieder auf also ich glaub zwar das die lösung kürzer sein kann aber nicht muss und das sich das ziemlich in waage hält

mfg

Michael

#17

im rätsel steht nirgens, daß das licht zu begin aus ist und woher soll der zähler wissen, daß er der erste ist?

#18

Hallo,

im rätsel steht nirgens, daß das licht zu begin aus ist und
woher soll der zähler wissen, daß er der erste ist?

Weil es der 1. Tag ist

#19

hmm, nun gut hast gewonnen.

#20

Programm?

Hallo,

Ich glaube, das muesste sich (mit Zufallszahlengenerator) sehr gut programmieren lassen. Dann kann man 10 0000 Versuche starten und sehen, wie lange es bei den verschiedenen Methoden im Mittel jeweils dauert. Interessant waere es allemal …

Man kann das ja beliebig verfeinern mit Super-Superzaehlern, etc. (Wenn ich dann echter Gefangener wäre, hätte ich natürlich Angst, dass einer einen Fehler macht und wuerde deshalb eher eine einfache Variante waehlen.) Aber fuer ein Computerprogramm ist es gut.

Seht schönes Rätsel! (*)