Aufgabe (100 Gefangene und 1 Glühbirne)[]
100 Gefangene werden zu lebenslänglicher Haft verurteilt. Sie erhalten allerdings eine Chance diese Strafe zu mindern. Sie werden für eine bestimmte Zeit in eine gemeinsame Zelle gesperrt und dürfen sich ein System für die folgende Prozedur ausdenken:
Dann werden die 100 Gefangenen in 100 Einzelzellen untergebracht, von denen aus
keine Möglichkeit besteht, miteinander zu kommunizieren. Jeden Tag wird einer von ihnen vollkommen zufällig ausgewählt und in einen Raum mit einer Lampe und deren Schalter
geführt. Dort DARF er den Schalter betätigen. Während dieser Prozedur
besteht keine Möglichkeit, den anderen Gefangenen andere Hinweise zu hinterlassen (z. B. Strichliste an der Wand, etc.) oder mit ihnen zu kommunizieren.
Sobald einer der Gefangenen dem Wächter sagt, dass bereits jeder Häftling mindestens einmal in der Zelle war und dies zutrifft, kommen alle Gefangenen frei. Stimmt dies nicht, haben sie keine weitere Chance ihre Haft zu verkürzen.
Können die Gefangenen ihre Freilassung erreichen? Wenn ja, wie?
[edit:] Lösungen sollten in eine oder mehrere der folgenden Kategorien fallen:
- sicheres System (Der Gefangene kann mit 100%-iger Sicherheit sagen, dass alle anderen in der Zelle waren)
- schnelles System (Einer der Gefangenen kann möglichst früh sagen, dass alle anderen drin waren. Dies muss nicht zwangsläufig mit absoluter Sicherheit sein. Die Sicherheit sollte aber besser sein, als die, die sich nach der entsprechenden Zeit schon allein aus stochastischen Berechnungen ergibt)
- neuartige / unkonventionelle Herangehensweise
- kreatives System (Auch wenn das ein Matheforum ist, sollten auch Scherzlösung der Art "Der letzte macht das Licht aus" erlaubt sein. Diese allerdings wirklich nur, falls sie wirklich kreativ sind)
Lösungen[]
Gefangene und Glühbirne, Lösung 1
Gefangene und Glühbirne, Lösung 2
Gefangene und Glühbirne, Lösung 3
Gefangene und Glühbirne, Lösung 4
Gefangene und Glühbirne, Lösung 5
Gefangene und Glühbirne, Lösung 6
Suchbegriffe[]
Gefangene, Glühbirne, Schalter, Information mit 1 bit
Quellen[]
Newsgroup de.sci.mathematik, Thread vom 31.Okt 2002
Spektrum der Wissenschaft, April 2003, S 108 und Juni 2003, S 110