Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / Sommerrätsel 2016
1 2 Previous Next  
- - By Frank Brenner Date 2016-08-25 01:39
Nachdem kürzlich ein eher mathematisches Problem behandelt wurde (und noch wird), hier jetzt ein Problem aus dem täglichen Leben das jeder im Kopf  lösen kann, auch ohne Programmierkenntnisse.

Ein König hält 97 Menschen in seinem Palast gefangen.


Er spricht zu den Menschen und erzählt Ihnen eine Möglichkeit wieder frei zu kommen:

Zunächst kommen alle Menschen ab dem nächsten Tag in eine Einzelzelle.
Anschließend wird an jedem Tag ein Mensch per Zufall ausgewählt und in einen kleinen Raum geleitet.
In diesem kleinen Raum ist eine kleine Leuchte die er ein- oder ausschalten kann.
Am Tag darauf kommt der Mensch wieder in seine Einzelzelle  und der nächste zufällig ausgewählte Mensch kommt in den  kleinen Raum und darf ebenfalls die Leuchte ein- oder ausschalten.

Jeder der 97  Menschen darf zu jedem beliebigen Zeitpunkt zum König und dem König mitteilen, dass jetzt jeder Mensch mindestens einmal im kleinen Raum gewesen ist.
Antwortet er richtig, so werden alle 97 Menschen freigelassen, ansonsten müssen alle 97 für immer im Gefängnis bleiben.

Nachdem der König den 97  Menschen den Sachverhalt erklärt hat,  haben die Menschen noch einen Tag Zeit um sich eine Strategie auszudenken, denn ab dem nächsten Tag beginnt die Einzelhaft und das Spiel beginnt.

Frage: Mit welcher Strategie können sich die Gefangenen zu 100% sicher sein eines Tages frei zu kommen ?

Wer die Lösung weiß, bitte nicht sofort hier verraten.

Hinweise:
Alle Menschen sehen und hören ab der Einzelhaft einander nie.
Der Mensch der als nächstes in den kleinen Raum kommt sieht, ob sein Vorgänger die Lampe ein oder ausgeschaltet verlassen hat.
Nur der Mensch im kleinen Raum sieht die Lampe.
Parent - - By Michael Bechmann Date 2016-08-25 09:05 Edited 2016-08-25 09:52
Kann es (wegen der Zufälligkeit der Auswahl des Gefangenen) möglich sein, dass einzelne der Gefangenen mehrfach den kleinen Raum besuchen oder sind am 97. Tag alle dort genau ein Mal gewesen und daher am 98. Tag ein neuer Zyklus beginnt?
(Darf der Gefangene nur genau einmal den kleinen Raum besuchen und die Gefangenen wissen auch, dass sie nur einmal dort hinkommen und sie in den Zellen eine Uhr haben wäre die Lösung leicht: Das Spiel endet genau am 97. Tag.)

Das führt zu einer anderen Frage:
Haben die Gefangenen eine Uhr oder mindestens ein Fenster zur Zelle oder kann er zumindest sich darauf verlassen, dass Brot und Wasser immer zu gleichen Uhrzeit eingeworfen werden?

Könnten die Gefangenen mehrfach mit der Wahrscheinlichkeit 1/97 für jeden Einzelnen den kleinen Raum besuchen, könnte eine Uhr auch eine wesentliche (vielleicht auch unerlässliche) Hilfe sein. Man könnte mit der Uhr oder dem Fenster (durch den Tag/Nacht-Rhythmus) verschiedene Tage unterscheiden.
Parent - - By Frank Brenner Date 2016-08-25 10:37
Die Menschen aus den Einzelzellen können auch mehrfach ausgewählt werden um in den kleinen Raum mit der Lampe zu kommen.
Daher ist es durchaus möglich, dass ein Mensch selbst nach 3000 Tagen noch kein einziges mal in den kleinen Raum war  während ein anderer bereits zufälligerweise 200 mal dort war.

Die Menschen können die Tage zählen. Eine Uhr um die exakte Uhreit abzulesen haben sie aber nicht und das Essen kommt irgendwann im Laufe des Tages.
Parent - - By Michael Bechmann Date 2016-08-25 11:14 Edited 2016-08-25 11:57
Es kam mir nur darauf an, ob ein Gefangener verlässlich erfährt, dass ein neuer Tag begonnen hat bzw. wie viele Besuche stattgefunden haben. Es reicht, das jeweilige Datum bzw. die Anzahl der vergangenen Tage zu wissen. Die exakte Uhrzeit ist nicht entscheidend.

Die Strategie muss ich mir noch genauer überlegen. Möglicherweise ist die Zahl 97 entscheidend damit das Rätsel funktioniert und die Zahl nicht beliebig vom König wählbar ist. Sonst könnte er doch auch 50 oder 100 oder eine andere Zahl Gefangene nehmen.

Andererseits: 1) Die angegebene Zahl 3000 (oder eine andere genügend hohe Zahl) wäre mir zu lang. Ich würde abschätzen oder auch nachrechnen (ich hätte doch Zeit), wie hoch die Wahrscheinlichkeit ist, dass alle im Zimmer waren und das kleine Rest-Risiko eingehen.

Geht es schief und ich dann lebenslänglich 96 Feinde hätte, würde ich sie trotzdem nie sehen.

2) Ich hätte sonst noch eine grobe und unmathematische Methode, die aber mit Sicherheit funktioniert. Aber ich weiß nicht, ob sie die Spielregeln erfüllt. Der König könnte regelmäßig mal nachsehen und wenn er feststellen würde, dass jemand im kleinen Raum randaliert hätte, könnte er für alle 97 Gefangenen den Verlust des Spieles erklären.
Parent - - By Frank Brenner Date 2016-08-25 12:44
Also die Menschen können jeden Tag ganz klar zählen.

Sicher, die Menschen könnten 1 Mio Tage warten, dann wäre mit an Sicherheit grenzender Wahrscheinlichkeit jeder bereits einmal im kleinen Raum gewesen, aber die Wahrscheinlichkeit dafür wäre kleiner als 100%. 

Gesucht ist eine Strategie die zu exakt 100% funktioniert.

Hierbei handelt es sich um ein reines Logikrätsel.

Die Lösung hat also nichts mit mutmaßlichen psychischen Verhaltensweisen von Menschen oder des Königs zu tun.
Parent - - By Benno Hartwig Date 2016-08-25 12:59
Auf den ersten Blick denkt man, dass das System nur 2 Zustände hat und meint "Ja, wie soll denn das gehen?".
Aber die Leute dürfen ja auch etwas vereinbart haben, feststellen und in ihrem Hirn behalten, und so kommen Zustände hinzu.
Und: Ja, es wird dauern, bis sie freikommen!

Benno
Parent - - By Frank Brenner Date 2016-08-25 13:16 Edited 2016-08-25 13:24
Ja, zweifellos.

Wie du weißt kann selbst nach 1 Milliarden Tagen  eine einzelne Person noch nicht im kleinen Raum gewesen sein. 
Allerdings ist die Wahrscheinlichkeit dafür viel kleiner als im Lotto zu gewinnen. Aus der Sicht einer einzelnen Person ist die Wahrscheinlichkeit (1-1/97)^(10^9)  in den ersten Milliarden Tagen nicht ausgewählt zu werden, das ist in etwa  3 x 10 hoch (-14)

Um 100% Sicherheit zu erzielen kann es unter Umständen sehr lange dauern.

So viel Mathe braucht man für die Lösung allerdings nicht.

Jeder hier im Forum wird die Lösung verstehen.

Ich hoffe ich habe mit diesem Hinweis nicht zu viel verraten. Es ist kein Spaßrätsel, sondern ein 100%iges Logikrätsel.
Parent - By Benno Hartwig Date 2016-08-25 14:42 Edited 2016-08-25 14:49

> So viel Mathe braucht man für die Lösung allerdings nicht.
> Jeder hier im Forum wird die Lösung verstehen.


Sicher hast du recht (ich kannte das Rätsel schon, bilde mir hier nichts auf meine Problemlösefähigkeiten ein.).

Interessant wäre aber auch mal zu klären, wie eigentlich der Erwartungswert für die Anzahl der Raumbesuche bis zur Freilassung wäre, wenn immer zufäliig gleichverteilt irgendeiner der 97 in den Raum geschickt würde.
Ich befürchte, dass das dann schon ganz schön dauern kann. Und das ganz ohne besonderes Pech.

Benno

PS:
Der König sollte übrigens auch gern zugesagt haben, dass er die Leute aber sämtlich auch immer mal wieder(!) in den Raum sendet.
Er darf nicht denken "Ach jetzt war jeder mal drin, mehr kann man von mir nicht erwarten! Jetzt schicke ich nur noch Meier und Müller zur Lampe!"
(Eine Präzisierung, und vielleicht auch ein Hinweis )
Parent - - By Peter Martan Date 2016-08-25 14:45
Benno Hartwig schrieb:

Und: Ja, es wird dauern, bis sie freikommen!

Und: Nein, man weiß nicht, wann das sein wird.

Aber: Ja, sie werden es schaffen.

Abgesehen von denen, die im Gefängnis sterben, weil sie das Pech hatten, schon zu alt oder zu krank zu sein, um König Zufall zu überleben.
Parent - By Benno Hartwig Date 2016-08-25 14:52

> Abgesehen von denen, die im Gefängnis sterben, weil sie das Pech hatten, schon zu alt oder zu krank zu sein, um König Zufall zu überleben.


Gute Ergänzung:
Wenn das Ableben den anderen nicht mitgeteilt wird, werden sie es ggf. nicht schaffen.
Und wenn ihnen das Ableben (einfach so) doch mitgeteilt wird, dann können sie gleich von vorn beginnen.
Also Beeilung, meine Herren!

Benno
Parent - By Frank Brenner Date 2016-08-25 14:56

> Abgesehen von denen, die im Gefängnis sterben


Der liebe Gott hat erbarmen mit den Menschen und lässt sie und den König sehr lange leben.

Das Rätsel spielt ja sowieso in einer idealisierten Welt, denn in einer realen Welt könnte man ja auch mit den Fingernägeln Markierungen an die Wände ritzen.
Parent - By Wolfram Bernhardt Date 2016-08-27 19:03
Wir hatten heute eine kleine Feier und ich habe dort dieses Rätsel erzählt. (mit 100 Gefangenen)
Und ich staunte nicht schlecht, als mein 13jährige Neffe sich mit diese Lösung meldete, die Du hier auch skizzierst:

Die Gefangenen einigen sich auf Intervall von 100 Tagen. Am jeweils ersten Tag schaltet der Gerufene die Lampe ein. An jedem weiteren Tag wird die Lampe in Ruhe gelassen - es sei denn ein Gefangener betrifft den Raum zum zweiten Mal innerhalb des Intervalls, dann schaltet er aus. Wenn am 100. Tag des Intervalls die Lampe noch brennt, meldet sich der an dem Tag Gerufene.

Natürlich ist diese Lösung schlechter als die mit dem Zählen und bedingt, dass die Gefangenen Tage zählen können. Und sie dauert auch ggf. sehr viel länger, weil ja erst ein Intervall stattfinden muss, in dem jeder Gefangene genau einmal gerufen wurde.

Trotzdem finde ich diese Lösung auch sehr hübsch.

Viele Grüße,
      Wolfram
Parent - - By Wolfram Bernhardt Date 2016-08-28 10:59
Hallo!

Ich hatte dies gestern schon einmal geschrieben, aber irgendwie ist das Posting jetzt nicht mehr da.
Mein 13. Jährigen Neffe, dem ich das Rätsel gestern gezeigt habe, hat mich mit einer Lösung erstaunt, die in die Richtung dessen geht, was Du hier andeutet:

Die Gefangenen verabreden sich zu Intervallen von 97 Tagen. Am ersten Tag wird die Lampe auf jeden Fall angeschaltet. Jeder weitere Gefangene lässt an den Folgetage die Lampe in Ruhe - es sei denn, er wird innerhalb des Intervalls zum zweiten Mal in den Raum geführt, dann schaltet er aus.
Wenn am letzten Tag die Lampe noch brennt, meldet sich der dann gerufene Gefangene zu Wort.
Wenn die Lampe aus ist, versucht man es ab dem nächsten Tag mit einem neuen Intervall.

Natürlich ist das schlechter als die Zähler-Lösung. Und man muss Tage messen und es dauert noch erheblich länger. Trotzdem finde ich diese Lösung auch sehr hübsch.

Viele Grüße,
     Wolfram
Parent - By Wolfram Bernhardt Date 2016-08-28 11:00
Und jetzt ist mein Posting von gestern wieder da... sorry.
Parent - - By Peter Martan Date 2016-08-25 12:49 Edited 2016-08-25 12:52
Frank Brenner schrieb:

Alle Menschen sehen und hören ab der Einzelhaft einander nie.
Der Mensch der als nächstes in den kleinen Raum kommt sieht, ob sein Vorgänger die Lampe ein oder ausgeschaltet verlassen hat.
Nur der Mensch im kleinen Raum sieht die Lampe.

Ist die Lampe eine, die beim Leuchten warm wird, und kann man sie angreifen, um ihre Temperatur zu spüren?
Ich gehe mal davon aus, dass jede andere Art, dem Nachfolger Informationen zukommen zu lassen, außer über die Lampe, unmöglich ist, sonst bräuchte man ja keine Lampe.
Parent - By Frank Brenner Date 2016-08-25 13:07
Hallo Peter,

die Lampe kann man nicht fühlen. Sie geht nur ein oder aus.  Bitte betrachte die Lampe als eine Binäre Informationseinheit (ein/aus) .  Auch die Lebensdauer, Farbtemperatur der Lampe, Temperatur im Raum ist undefiniert und für die Lösung des Rätsels bedeutungslos. Es ist selbstverständlich auch nicht möglich den Raum zu verändern durch anritzen oder sowas.

Grüße
Frank
Parent - - By Ingo Althöfer Date 2016-08-25 15:24
Ein hübsches Rätsel, danke dafür.
Letztes Jahr im Sommer kursierte es bei der Computer-Olympiade in Leiden.

Meine Lösung funktioniert nicht nur für 97, sondern auch für jede andere
endliche (bekannte) Zahl n. Im Durchschnitt brauchen die Gefangenen
mehr als n-hoch-2 und weniger als 2 mal n-hoch-2 Tage.

Ingo Althöfer.
Parent - By Frank Brenner Date 2016-08-25 15:37
In der Tat kann n (hier 97)  beliebig sein, außerdem ist es nicht erforderlich, dass die Menschen die Tage zählen können.

Ich habe das Rätsel per Zufall gestern abend im Internet entdeckt und fand es so gut weil es erstens kein Scherzrätsel ist und zweitens einen sehr leichten Sachverhalt hat und drittens weil jeder die Lösung versteht und viertens weil ich annehme, dass nur sehr wenige die Lösung  finden.
Parent - - By Timo Haupt Date 2016-08-25 17:58
Hallo Ingo,

ich war zwar auch letztes Jahr in Leiden dabei, habe aber leider das Rätsel dort verpasst. Deine Lösung ist wohl schon ziemlich gut, denn weniger als 2*n^2 Tage erscheint mir eine sehr kurze Zeit zu sein. Bei meiner vorläufigen Lösung liege ich in einem Bereich von größer 10 hoch 300 Tagen für 100 Gefangene. Es wäre also im realen Leben quasi unmöglich, dass die Gefangenen freikommen - die Wahrscheinlichkeit dafür, dass das passende Ereignis noch in der Lebenszeit der Gefangenen eintritt, wäre einfach zu gering.

Ich muss noch etwas genauer nachdenken, um in die Nähe deiner Lösung zu kommen, die ja auch im wirklichen Leben durchaus zu einer Strafmilderung führen könnte, wenn es nicht mehr als ca. 50 Gefangene wären.

Viele Grüße
Timo

P.S.: Vielen Dank an Frank für dieses schöne Rätsel!
Parent - - By Ingo Althöfer Date 2016-08-25 18:55
Hallo Timo,

Timo Haupt schrieb:
ich war zwar auch letztes Jahr in Leiden dabei,
habe aber leider das Rätsel dort verpasst.

Es war (am Do?!) in dem Innenhof, wohin die ganze Baggage einen Nachmittags-
Ausflug (mit Buffet) gemacht hatte. Weil nicht alle gleichzeitig ankamen,
vertrieben sich einige "early birds" (auch Mark Lefler) die Zeit mit Logik-
Rätseln. Guy Haworth erzählte das Gefangenen-Rätsel.

Zitat:
Deine Lösung ist wohl schon ziemlich gut, denn weniger als
2*n^2 Tage erscheint mir eine sehr kurze Zeit zu sein.

Um ehrlich zu sein: Die Lösung gefunden hat jemand anderes (weiss
nicht mehr, wer). Ich habe dann nur die Abschätzung der erwarteten
Tagezahl gemacht.

Zitat:
Bei meiner vorläufigen Lösung liege ich in einem Bereich
von größer 10 hoch 300 Tagen für 100 Gefangene...

Interessant. Wenn es vorbei ist, musst Du Deine Lösung auch
hier zeigen.

Viele Grüße, Ingo.
Parent - - By Timo Haupt Date 2016-08-27 12:32 Edited 2016-08-27 12:35
Hallo Ingo,

als dein Tipp (weiter unten im Thread) mit dem einen Zähler kam, dämmerte es mir auch langsam, dass es viel einfacher und schneller geht als mit meiner Lösung. Diese sieht so aus:

Da die Gefangenen die Tage zählen dürfen, geben sie sich in der Besprechung vorab jeweils eine Nummer für einen Tag. Der Gefangene mit der Nummer 1 steht also für den Tag 1 usw. Die Tageszählungen der Gefangenen beginnen immer mit Tag 1 und enden mit Tag 97, danach beginnt die Zählung wieder bei 1. Immer dann, wenn ein Gefangener an einem Tag in den Raum mit der Lampe geführt wird, der seiner Nummer entspricht, schaltet er die Lampe ein, falls sie ausgeschaltet war. War die Lampe bereits eingeschaltet, notiert er dies auf seinem (geistigen) Zettel, kann also bei dem Gefangenen mit der Nummer x-1 (x sei seine eigene Nummer) einen Haken machen und lässt die Lampe brennen, damit der Nachfolger weiß, dass auch er an dem richtigen Tag in den Raum geführt wurde. Wird ein Gefangener mit einer Nummer in den Raum geführt, die nicht der Nummer des aktuellen Tages entspricht, verlässt er den Raum bei ausgeschaltetem Licht. Er notiert aber trotzdem, ob die Lampe eingeschaltet war, als er den Raum betrat, denn dann kann er auf seiner Liste den Gefangenen mit der Nummer des Vortages abhaken. Derjenige, dessen Liste zuerst voll ist, kann dem König mitteilen, dass alle 97 Gefangenen mindestens einmal im Raum waren.

Meine ursprüngliche Überlegung zur Berechnung der ungefähren Dauer war falsch, da ging ich von 97!*97! (= ca. 9*10^303) aus. Leider bin ich ratlos, wie man den Erwartungswert (für die Dauer in Tagen) meiner Lösung berechnen könnte...

Viele Grüße
Timo
Parent - - By Peter Martan Date 2016-08-27 13:09
Entschuldige, Timo, aber irgendwie verstehe ich dich nicht.
Gehst du davon aus, die Reihenfolge und damit die Zahl der Tage, die es dauert, bis sie das erste oder das wiederholte Mal an den Lichtschalter kommen, habe irgendetwas mit den Nummern zu tun, die sie einander selber geben, oder stehe ich nur wieder auf der Leitung?
Parent - - By Timo Haupt Date 2016-08-27 13:23
Hallo Peter,

es geht lediglich um die transportierte Information für den Nachfolger, dass ein Häftling mit einer bestimmten Nummer schon in dem Raum war. Bei mir spielt die Tatsache keine Rolle, ob derjenige das erste oder schon zum x-ten Mal in dem Raum war. Das ist auch der Grund, warum meine Lösung viel länger dauern wird. Ich habe zwar nicht nur einen Zähler, sondern quasi 97 Zähler, aber bei mir wird halt nur "gezählt" (bzw. auf der Liste abgehakt), wenn zufällig mal ein Häftling mit der vorher bestimmten Nummer x auch an dem Tag x in dem Raum mit der Lampe war. Nur dann würde er das Licht einschalten und der Nachfolger kann erkennen, dass Häftling Nummer x bereits mindestens einmal im Raum war. Irgendwann wird die Liste von irgendeinem der Häftlinge voll sein, aber das kann aus verständlichen Gründen seeeeeeeeeeeeeehr lange dauern. Denn es wird eben auch etliche 97er Zyklen geben, in denen kein einziger Häftling genau an "seinem Tag" in den Raum geführt wird und somit die Lampe gelöscht bleibt. Dazu kommt, dass sich die Listen der Häftlinge unterschiedlich schnell füllen und es so sein kann, dass irgendwann ein oder mehrere Häftlinge zwar eine Liste von bereits 96 abgehakten Einträgen haben, aber partout sich Eintrag Nr. 97 nicht einstellen mag, da sie nicht an dem passenden Tag in den Raum geführt werden, der genau nach dem noch offenen Eintrag liegt. Und selbst wenn das passiert, muss vorher genau der passende Häftling mit der Nummer des Tages in dem Raum gewesen sein, da sonst ja die Lampe nicht eingeschaltet würde.

Gruß
Timo
Parent - - By Peter Martan Date 2016-08-27 14:17 Edited 2016-08-27 14:29
Jetzt hab ich dich, glaube ich, verstanden, nur noch zur Sicherheit dein Prinzip anders formuliert, wie ich es verstehe:

Nur wer zufällig zu einem bestimmten Zeitpunkt, einer eigenen vereinbarten Zeit- und Nummerrechnung folgend, dran kommt, macht Licht, alle anderen lassen es brennen, wenn's der (auch schon recht große) Zufall will, dass sie unmittelbar nacheinander zeitlich passen, oder machen es aus, wenn's nicht ihr Tag ist.
Ich glaube schon, dass das auch funktionieren sollte, mein Einwand gegen die Forumulierung des Rätsels bliebe aber derselbe.

Muss es im Fall des Einzelzählers der Zufall wollen, dass es nicht immer den Selben immer wieder und auch nicht den Erwählten niemals trifft, muss es bei dir der Zufall wollen, dass irgendwann alle an ihrem ausgemachten Tag dran waren, und ein anderer oder wieder zufällig der selbe hat dann irgendwann soviele derartige Treffer gezählt, war also seinerseits wieder zufällig im richtigen Zeitpunkt der Nächste, zum Zählen Gelegenheit zu haben.

Ist es im Fall des Einzelzählers zwar sehr unwahrscheinlich, dass gerade der nie drankommt, (in einem begrenzten Zeitraum) ist es in deinem Fall für mich eher unwahrscheinlich, dass es in einem Zeitraum passiert, der für mathematische Laien noch gefühlsmäßig von "praktisch endlos" unterscheidbar ist.


Bin neugierig auf die Durchrechnung der Mathematiker für dein Prinzip.
Parent - By Timo Haupt Date 2016-08-27 16:22
Genau richtig erklärt, Peter!

Während bei der schnelleren Lösung (ein "Zähler") es im Durchschnitt alle 97 Tage zu einem Fortschritt kommen kann (nämlich dann, wenn der Zähler in den Raum geführt wird - Voraussetzung ist natürlich, dass in den vorherigen Tagen jemand anderer zum ersten Mal in den Raum geführt worden ist), ist es in meinem Fall nur möglich, wenn jemand exakt an seinem vorher bestimmten Tag in den Raum kommt. Und das bekommt dann eben leider nicht der eine Zähler mit, sondern der nächste in den Raum Geführte, damit dieser erkennen kann, dass Häftling Nr. X jetzt dran war. Im schlimmsten (noch endlichen) Fall müssen bei mir erst alle 97 Häftlinge ihre Listen bis zur auf eine vakante Position aufgefüllt haben, bis bei irgendeinem dann der erlösende 97. Eintrag kommt. Das wird deutlich länger dauern als bei der besseren Lösung, selbst wenn da der Zähler nur alle 1.000.000 Tage in den Raum geführt werden sollte (was schon äußerst unwahrscheinlich wäre)...
Parent - - By Michael Bechmann Date 2016-08-25 19:36
Die brachiale Methode wäre, dass der erste Gefangene die Lampe in 97 Scherben schlägt. Jeder, der zum ersten Mal in den Raum kommt, zieht genau eine Scherbe und nimmt sie mit.
Beim nächsten Besuch nimmt er keine weitere Scherbe mit.

Wer die letzte Scherbe findet, kann dem König melden, dass alle da gewesen sind. 
Es heißt doch nicht, dass die Lampe funktionieren muss.
Parent - - By Frank Brenner Date 2016-08-25 19:43
Leider ist das nicht möglich.

Bitte stell die eine idealisierte Weltvor: Das Lampe kann nicht zerteilt werden, der Raum nicht markiert und es können auch keine Haare oder Fingerabdrücke auf dem Boden hinterlassen werden und kein Mensch stirbt solange das Spiel im Gange ist.

Es ist ein reines Logikrätsel. Die Lösung enthält auch keine Komponente wo man sagen könnte "Achso, ich wusste nicht dass man das auch darf, das hättest du ja vorher sagen können"
Parent - - By Ingo Althöfer Date 2016-08-25 19:52
Lieber Herr Brenner,

Frank Brenner schrieb:
Leider ist das nicht möglich...Es ist ein reines Logikrätsel.

Sie haben natürlich völlig recht.

Aber trotzdem: die Lösung von Herrn Bechmann enthält mehr
als ein Körnchen Weisheit.

Seitenfrage: Wenn es im Bechmann'schen Sinne ginge, was wäre die erwartete
Anzahl Tage, bis die Gruppe frei kommt?

Ingo Althöfer.
Parent - By Michael Bechmann Date 2016-08-25 20:10 Edited 2016-08-25 20:26
Mit der Seitenfrage habe ich mich heute Vormittag bereits beschäftigt. Ich kam (voreilig) auf den falschen Weg, dass man eine entsprechende Wahrscheinlichkeit mit einer Binomial-Verteilung ausrechnen könnte.

Später viel mir auf, dass man allenfalls so berechnen kann, wie hoch die Wahrscheinlichkeit in gegebener Tagesanzahl verschiedene Anzahlen der Gänge zum Lampenraum ist.
(Also mit welcher Wahrscheinlichkeit in z. B. 1000 Tagen nie, 1 mal,... 10 mal usw.) zum Lampenraum geht.

"Aus der Sicht einer einzelnen Person ist die Wahrscheinlichkeit (1-1/97)^(10^9) " - Mit dieser Formel bekommt man keine Wahrscheinlichkeit, dass alle schon in diesem Raum waren. Auch dafür viel mir so schnell keine Formel ein.
Eine Formel für die Wahrscheinlichkeit, dass alle Gefangenen (abhängig der Tagesanzahl) schon im Lampenraum waren würde mich interessieren.

Letztlich aber soll es gar nicht um Wahrscheinlichkeiten gehen sondern eine exakte logische Lösung mit einem ganz konkreten Algorithmus.
Somit ist auch mein erster Vorschlag, nach hinlänglich langer Zeit ein kleines Risiko einzugehen, hinfällig.
Parent - - By Michael Bechmann Date 2016-08-25 22:20 Edited 2016-08-25 22:39
Zitat:
"Bitte stell die eine idealisierte Welt vor" 


Haare und Fingerabdrücke also Hinweise für nachfolgenden halte ich für Quatsch. Wer weiß denn, ob nicht am 389. Tag eine Putzfrau kommt und alles säuberlich entfernt.

Ich will es nun doch mal mit Logik versuchen, es bleibt wohl nichts anderes übrig:
Eine Kommunikationsform (wenn auch eine sehr rudimentäre) gibt es auf jeden Fall, auch wenn ansonsten nach Regel keine Kommunikation stattfinden darf:
nämlich darauf zu achten, ob die Lampe brennt oder eben nicht.
Es wird eventuell auch die einzige Information und somit der Schlüssel der Lösung sein.

Man muss 1) eine richtige Schlussfolgerung aus dem "AN" oder "AUS" vom Vorangegangenen ziehen    und 2) sinnvoll entscheiden, wie er die Lampe für den Nachfolgenden hinterlässt. (*)
Sie sollten den einen Tag nutzen um ein gutes System in diesem Sinne zu finden, das alle verstehen und das alle konsequent durchführen.

Es entsteht im Laufe der Zeit eine Art binäre Folge der Leuchtzustände vorstellen (etwa AUS/AN/AN/AN/AUS...). Hier besteht aber die Schwierigkeit, dass der hereingeführte Gefangene nur den letzten Zustand sieht (AUS oder AN).
Er hat also keinen Überblick auf den gesamten Verlauf der Folge (also die einzelnen Zustände der Lampe) für alle vergangenen Tage.

(Den gesamten Verlauf der Reihenfolge der hereingeführten Gefangenen und auch, wie sie für die Lampe entschieden haben, hat allenfalls der König. Der müsste allerdings wissen, ob alle 97 schon an der Lampe waren. Er wird aber den Gefangenen natürlich nicht verraten, ob alle schon an der Lampe waren.)

Das Hauptproblem ist wohl, das es keinen der 97 gibt, der die Übersicht hat, sondern jeder, der im Raum war nur einzelne Informationen (Leuchtzustände die er vorgefunden hat) bekommt.
So würde ich (als einer der Gefangenen) anregen, dass man ein System findet, welches für alle Gefangenen alle Zustände der Lampe im Sinne von (*) erkennt und daraus auch erkennen kann, wieviele schon mindestens einmal in dem Lampenraum waren.
Parent - - By Benno Hartwig Date 2016-08-25 23:27
Es ist nicht nötig dass alle Überblick haben.
Und die komplette Kenntnis des "gesamten Verlaufs der Reihenfolge der hereingeführten Gefangenen und auch, wie sie für die Lampe entschieden haben" ist auch bei niemandem nötig.
Parent - - By Michael Bechmann Date 2016-08-26 01:44 Edited 2016-08-26 01:51
Ich will es mal radikal vereinfachen. Bei komplizierten Sachverhalten hilft es oft, den Mechanismus des Sachverhaltes zu begreifen.

Wenn der vereinfachte Fall verstanden ist kann man versuchen, ob auch komplizierte Fälle nach dem gleichen Muster lösbar sind.

Statt 97 sollen mal nur 3 Gefangene sein. Da kann man ein Baumdiagramm in eben noch vertretbaren Aufwand für alle Varianten erstellen.

Wir, das Gefangenenkollektiv, vereinbaren ein relativ simples System:
I. dass am 1. Tag das Licht AN gemacht wird, egal, wer dran kommt.
II. nur, wer das erste Mal in den Raum geführt wird ändert den Lichtzustand. Wer wiederholt in den Raum kommt, macht nichts. 

Ich nehme mal an, dass ich Nr.1 bin. (Ist Nr.2 oder Nr.3 am 1. Tag dran ändert das das System nicht. Es wird analog verfahren.)

Tag 1: Ich werde ausgewählt. Ich mache das Licht AN.

          Tag 2:  a) Ich bin wieder ausgewählt. Das Licht bleibt an.

                          Tag 3: Ein anderer wird ausgewählt und der muss nun das Licht AUS schalten. Das bedeutet für den 4. Tag (egal, wer da dran ist): "Es sind noch nicht alle dran gewesen."

                      b) Nr.2 ist dran. Gemäß Regel II schaltet er das Licht aus.

                                   Tag 3: bA) Ich (Nr.1 ) oder wieder Nr.2 ist wieder gewählt. Das Licht bleibt AUS (weil Nr.1 oder Nr. 2 "Wiederholer" sind, vgl. Regel II). Das heißt, das Nr.3 noch nicht dran war.
                                             Am 4. Tag wird man einen dunklen Raum vorfinden und das bedeutet wie im Fall a): "Es sind noch nicht alle dran gewesen."

                                            bB) Nach Nr.1 und nach Nr.2 wird Nr.3 zur Lampe geführt. Nr.3 war noch nicht dort und muss nach Regel I das Licht wieder AN schalten. Wer am 4. Tag einen erleuchteten Raum findet,
                                           kann zum König gehen und erklären, wir sind alle dort gewesen.

                      c) Nr.3 ist dran.  Gemäß Regel II schaltet er das Licht aus.

                                    Tag 3: cA) Nr.1 oder wieder Nr.3 gewählt: Lampe bleibt AUS. --> "Nr.2 war noch nicht da, also waren noch nicht alle drangewesen."

                                              cB) nach Nr.1 und Nr.3 wird Nr.2  zur Lampe geführt. Nr.2 war noch nicht dort und muss nach Regel I das Licht wieder AN schalten. Wer am 4. Tag einen erleuchteten Raum findet,
                                              kann zum König gehen und erklären, wir sind alle dort gewesen.

Auch, wenn 3 mal nacheinander zur Lampe geführt wurde, ist die Lampe am 4. Tag AUS.

In allen Varianten kann jeder am 4. Tag erkennen, ob alle 3 an der Lampe waren: Licht AN --> alle dagewesen  oder Licht AUS --> einer fehlt noch.

Es wäre zu prüfen (aber nicht in dieser Nacht von mir), ob die Lösung so aussieht: bei n (z. B. n=97) am (n+1). Tag die Lampe leuchtet (Alle n Gefangenen durch gewesen) oder, wenn die Lampe AUS ist, noch einer fehlt.
Parent - - By Peter Martan Date 2016-08-26 08:32
Michael Bechmann schrieb:

Es wäre zu prüfen (aber nicht in dieser Nacht von mir), ob die Lösung so aussieht: bei n (z. B. n=97) am (n+1). Tag die Lampe leuchtet (Alle n Gefangenen durch gewesen) oder, wenn die Lampe AUS ist, noch einer fehlt.

Ich hoffe wirklich, Frank prüft das bald und wenn's doch wieder nicht stimmt, löst er es zeitnahe auf, ich beginne es zu hassen. Ich fürchte allerdings, du irrst dich auch, er hat ja irgendwo noch geschrieben, die Gefangenen brauchen die Tage gar nicht zu zählen.
(Zugegeben, ich hatte schon ein paar Fehlversuche per PM mit ihm, sowas verdirbt's einem dann )
Parent - - By Benno Hartwig Date 2016-08-26 09:03
Man ist auf dem Holzweg, wenn man meint, dass man nur die Information "Lampe an oder aus"  für die Zustandsbeschreibung des Systems hat.
Jeder der Gefangenen (die ja einen gemeinsamen, abgesprochenen Plan verfolgen!) hat ja darüber hinaus die komplette Historie seiner eigenen Lampenbesuche im Kopf.
Wie oft war er dort? War dann die Lampe da aus oder an? Und was hat er dann jeweils selbst getan?

Benno
Parent - - By Peter Martan Date 2016-08-26 10:22
Ja, danke, verstehe.
Dennoch, eigentlich hasse ich das am meisten, wenn man erst an der Hand Schritt für Schritt an die Lösung von so einem Sch...önen Rätsel herangeführt wird.

Nein, Scherz beiseite, echt gut das Ding.
Parent - - By Ingo Althöfer Date 2016-08-26 11:59
Lieber Herr Martan,

Peter Martan schrieb:
... eigentlich hasse ich das am meisten, wenn man erst
an der Hand Schritt für Schritt an die Lösung von so einem Sch...önen Rätsel
herangeführt wird.

trotzdem ein letzter Tipp von mir:
nur einer der Inhaftierten muss zählen können;
bei allen anderen reicht, dass sie merken, wann ein erstes Mal ist.

Ingo Althöfer.
Parent - - By Peter Martan Date 2016-08-26 13:08
Ingo Althöfer schrieb:

trotzdem ein letzter Tipp von mir:
nur einer der Inhaftierten muss zählen können;
bei allen anderen reicht, dass sie merken, wann ein erstes Mal ist.


Ehrlich gesagt glaub ich nicht wirklich, sehr geehrter Herr Professor, dass sie mir damit helfen wollen.
Weil wer der eine ist, der zählen können muss, weiß ja weder der, noch wissen es die Anderen.
Aber wenn's so gemeint war, wie ich glaube, ist das ein lustiger Tip.
Parent - - By Ingo Althöfer Date 2016-08-26 13:19
Lieber Herr Martan,

Peter Martan schrieb:
Ehrlich gesagt glaub ich nicht wirklich, sehr geehrter Herr Professor,
dass sie mir damit helfen wollen.

Was soll das denn heissen? Da müht man sich ab ...

Zitat:
Weil wer der eine ist, der zählen können muss, weiß ja
weder der, noch wissen es die Anderen.

Doch! Deshalb haben die Leidensgefährten ja zu Beginn
eine gemeinsame Sitzung, in der sie sich beraten und auch
den Zähler ausgucken dürfen.

Mehr können "wir" jetzt aber beim besten Willen nicht verraten.

Ingo Althöfer.
Parent - By Peter Martan Date 2016-08-26 15:38 Edited 2016-08-26 15:47
Ingo Althöfer schrieb:

Zitat:
Weil wer der eine ist, der zählen können muss, weiß ja
weder der, noch wissen es die Anderen.

Doch! Deshalb haben die Leidensgefährten ja zu Beginn
eine gemeinsame Sitzung, in der sie sich beraten und auch
den Zähler ausgucken dürfen.

OMG, ich wusste ja, es hat eigentlich nichts mit Binärsystem, Mathematik oder einem anderen Sch...marrn zu tun.

Danke, ich denke, jetzt hab ich's doch endlich geschnallt. PMs schreibe ich jetzt aber keine mehr, um meine Vorstellung zu verifizieren, wenn's wieder falsch ist, verkrafte ich das nicht mehr.


P.S.
Ingo Althöfer schrieb:

Peter Martan schrieb:
Ehrlich gesagt glaub ich nicht wirklich, sehr geehrter Herr Professor,
dass sie mir damit helfen wollen.

Was soll das denn heissen? Da müht man sich ab ...


Das war einfach die Paranoia Desjenigen, der vom Wissenden mit jeweils gerade soviel Info versorgt wird, dass er sich nur umso dümmer vorkommt, anstatt endlich zur Erkenntnis zu gelangen.
Man fühlt sich dann manchmal einfach gefrotzelt, wie wir bei mir zu Hause sagen, verzeihen Sie mir das, lieber Herr Professor.
Parent - By Benno Hartwig Date 2016-08-26 08:58 Edited 2016-08-26 09:06

> Es wäre zu prüfen...


Ich denke, dein Ansatz kann nicht unterscheiden, ob z.B. nach 10 Tagen 5 Leute oder 7 oder 3 im Raum waren.
(Trotzdem ist der Ansatz nicht schlecht!)


Benno
Parent - - By Frank Brenner Date 2016-08-26 12:55
Hallo Michael,

> I. dass am 1. Tag das Licht AN gemacht wird, egal, wer dran kommt.
>II. nur, wer das erste Mal in den Raum geführt wird ändert den Lichtzustand. Wer wiederholt in den Raum kommt, macht nichts. 


Leider klappt das so nicht:

Nehmen wir an, bei drei leuten kommen alle zufälligerweise der Reihe nach dran:

der erste macht das licht an, der zweite aus, und der dritte macht es an.

Danach bleibt es für immer an.

Wer von den dreien sollte dann jemals wissen dass es genau 3  leute sind ?

Wenn ich (ich bin der 1. , 2. oder 3.) nach einiger zeit nochmal ausgewählt werde sehe ich eine leuchtende  Lampe.  Ich kann aber nicht entscheiden ob in der zwischenzeit nur "Widerholer" ausgewählt wurden oder ob in der Zwischenzeit 2 Neulinge dazugekommen sind, welche die lampe aus und wieder ein geschaltet haben.
Parent - - By Michael Bechmann Date 2016-08-26 22:41 Edited 2016-08-26 22:48
Nochmal im Bsp. mit nur 3 Gefangenen:

>"der erste macht das licht an, der zweite aus, und der dritte macht es an."


Genau deswegen funktioniert mein System doch. Wenn der dritte das Licht wieder angemacht hat, erkennt der Kandidat am 4. Tag genau das: Es waren alle dran gewesen.

>" Ich kann aber nicht entscheiden ob in der zwischenzeit nur "Widerholer" ausgewählt wurden "


Doch. Wenn mindestens einer ein Wiederholer sein sollte ist die Lampe am 4. Tag aus.- siehe Beitrag der letzten Nacht mit dem Variantenbaum.
Parent - - By Frank Brenner Date 2016-08-26 23:18 Edited 2016-08-26 23:22
Nachdem der dritte die Lampe  angemacht hat, kommt in den nächsten 27 Tagen stets jedesmal der dritte erneut dran und belässt die Lampe an. (gemäß II)

Danach kommt der erste oder zweite per zufall wieder (wiederholt) dran. Wie sollen die beiden dann wissen dass sie insgesamt nur zu dritt sind ?

> Doch. Wenn mindestens einer ein Wiederholer sein sollte ist die Lampe am 4. Tag aus.- siehe Beitrag der letzten Nacht mit dem Variantenbaum.


Bitte  lies Dir nochmal deine beiden Bedinungen I. und II durch:  Nachdem alle 3 einmal in den Raum waren , ändert sich das Leuchtverhalten der Lampe nicht mehr.

Dein Variantenbaum enthält ausserdem mindestens eine verkehrte schlußfolgerung und zwar: Tag 3 bB: Derjenige der am Vierten Tag ausgewählt wurde kann überhaupt nicht sagen dass es nur 3 sind. Es könnten nämlich beliebig viel mehr als 3 sein die nur noch nicht dran waren.
Parent - - By Michael Bechmann Date 2016-08-27 00:06 Edited 2016-08-27 00:45

>"  Nachdem alle 3 einmal in den Raum waren , ändert sich das Leuchtverhalten der Lampe nicht mehr."


Richtig! Es muss das Leuchtverhalten sich auch nicht mehr ändern, denn wenn alle 3 einmal im Raum waren und man das durch logischen Denken auch erkennt ist das Spiel zu Ende.

Zu Fall bB) Nr.1 macht die Lampe AN, Nr.2 schaltet sie aus und Nr.3 schaltet sie wieder an. Das ist das Zeichen, dass alle dran waren.
Wäre ein Wiederholer an den 3 Tagen da gewesen, wäre die Lampe am 4. Tag aus.

>"Derjenige der am Vierten Tag ausgewählt wurde kann überhaupt nicht sagen dass es nur 3" -


In meinem vereinfachten Fall schon, weil ich von Anfang an nur mit 3 (statt 97) rechnete und so wussten dann auch die Kandidaten, das es nur 3 gibt.

Ich muss aber zugeben, dass bei dem Fall, dass immer der gleiche am 3. Tag dran war, eine Korrektur nötig ist:
III. Regel: Wenn zufälligerweise immer der gleiche Kandidat dran war muss er die Lampe am 2. Tag ausschalten und sie auch am 3. und folgenden Tagen aus lassen um andere zu signalisieren, dass noch nicht alle an der Lampe waren.
Dann würde sich aber ein neues Problem ergeben: Wenn Kandidat 1 und am Tag 1 und 2 dran war, würde ein anderer am 3. Tag die Lampe einschalten und am 4. Tag wäre die Lampe immer noch an obwohl der dritte Kandidat noch NICHT dran war.
Man müsste eine weitere IV. Regel einführen --- Aber eigentlich wollte ich ein einfaches System finden
Parent - - By Frank Brenner Date 2016-08-27 00:42

> III. Regel: Wenn zufälligerweise immer der gleiche Kandidat dran war ....


Leider bist du noch weit von der Lösung entfernt.

Die Lösung ist einfacher.

Ein Tipp: Herr Althöfer hat hier im Thread bereits einen Teil der Lösung mitgeteilt.
Parent - - By Michael Bechmann Date 2016-08-27 00:45
Zitat:
  Im Durchschnitt brauchen die Gefangenen mehr als n-hoch-2 und weniger als 2 mal n-hoch-2 Tage.


Bei n=97 also zwischen 9409 (knapp 26 Jahre) bis 18050 (knapp 50 Jahre). Das klingt aber auch eher nach einer hochkomplizierten Logik und für n=97 wegen rund 26 bis 50 Jahre auch nicht praktikabel.

Es ist wohl aber so, dass ein völlig neuer Denkansatz nötig ist.
Parent - By Frank Brenner Date 2016-08-27 00:58
Die lange Zeit von 26 Jahren  ist ja (meiner Meinung nach) der Grund dafür, dass das Rätsel für Menschen so schwer zu lösen ist obwohl die Lösung sehr kurz und einfach  ist und  sofort verstanden wird: Es ist nämlich so, dass rund 98% der  Besuche im kleinen Raum nutzlos sind. Menschen können so nicht denken und versuchen stattdessen an jedem einzelnen Besuch eine  lösungsrelevante Information zu extrahieren.
Parent - - By Ingo Althöfer Date 2016-08-27 08:33
Lieber Herr Bechmann,

ein bißchen kann ich Ihre Verzweiflung verstehen. Wenn Herr Martan
nicht inzwischen "kuriert" wäre, sollten Sie mit ihm eine Selbsthilfe-
Gruppe gründen. Es könnten dann auch weitere hinzustossen, die sich
nicht zu schreiben trauen.

Michael Bechmann schrieb:

Zitat:
  Im Durchschnitt brauchen die Gefangenen mehr als n-hoch-2 und weniger als 2 mal n-hoch-2 Tage.

Bei n=97 also zwischen 9409 (knapp 26 Jahre) bis 18050 (knapp 50 Jahre).
Das ...ist für n=97 wegen rund 26 bis 50 Jahre auch nicht praktikabel...

Je länger ich darüber nachdenke, umso mehr gefällt mir Ihre Lösung mit den
97 Scherben. Insbesondere ergibt sich dabei eine deutlich kürzere erwartete
Zeit, nämlich bei n Gefangenen nur etwa n*log(n) statt n^2, wobei hier der
Logarithmus zur Basis e gemeint ist.
Setzt man grob log(97) < 6, so ergeben sich im Durchschnitt
97*6 ca= 600 Tage, was nicht so arg wäre.

Grüße von einem, der sich heute nacht keinen
auf die Lampe gegossen hat,

Ingo Althöfer.
Parent - By Michael Bechmann Date 2016-08-27 08:43
Hallo,

ich habe vorhin einen neuen Denkansatz vorgestellt mit 6 Regeln. Es scheint - zumindest für wenige Gefangene - zu funktionieren.

Wie lange die Prozedur (Anzahl der Tage bis alle dran gewesen sind) im Mittelwert sein wird, bleibt noch zu klären.
Parent - - By Peter Martan Date 2016-08-27 10:40 Edited 2016-08-27 10:54
Ingo Althöfer schrieb:

ein bißchen kann ich Ihre Verzweiflung verstehen. Wenn Herr Martan
nicht inzwischen "kuriert" wäre, sollten Sie mit ihm eine Selbsthilfe-
Gruppe gründen. Es könnten dann auch weitere hinzustossen, die sich
nicht zu schreiben trauen.


Irgendwie werde ich das Gefühl schon wieder nicht los, sehr geehrter Herr Professor, dass sie sich doch ein bisschen an der "Verzweiflung" der Erfolglosen erfreuen, woher kommt das nur immer bei mir?

Mittlerweile haben Sie Michaels letzte Lösung doch für gut befunden. Hat sich Frank da also zunächst auch geirrt?

http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=102957#pid102957

Meine Lösung, die aus wie mir mittlerweile umso triftiger scheinenden Gründen nicht an Frank oder Sie per Private Message ging (nein, hier kein Misstrauen außer gegen meine eigene Lösung ) dürfte nämlich wohl doch auch falsch sein.

Ich zweifle an meiner und damit auch an Michaels Lösung unter anderem aus folgendem Grund:
Rein theoretisch (bei 3en oder 13 weniger aber auch) besteht doch auch die Möglichkeit, dass der Zähler überhaupt nie ins finstere oder spärlich beleuchtete Verlies kommt, nein?
Spricht da irgendetwas dagegen außer der Wahrscheinlichkeitsrechnung?
Und sagt die über das Einzelereignis überhaupt etwas aus?
Und wäre es nicht bei einem irgendwie begrenzten Beobachtungszeitraum nur eine umso mehr gegen 100% gehende Wahrscheinlichkeit, die in Franks Version formuliert wird, die die Lösung erlaubt, und müsste man einen unbegrenzten Zeitraum nicht auch bei diesen ohnehin unrealistischen Vorgaben in Rechnung stellen?

Sorry, ich bin offenbar einfach auch nach wie vor auf dem Holzweg, richtig?
Up Topic Hauptforen / CSS-Forum / Sommerrätsel 2016
1 2 Previous Next  

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill