Uhrenstellende Gefangene [Yoni's Riddles 9/15]

Freizeit & Hobby Rätsel
#1

100 Männer sind in einem Gefängnis. Der Gefängnisverwalter, welcher Rätsel liebt, gibt den Männern die Möglichkeit freizukommen.
Im Gefängnis gibt es einen Raum mit einer großen Uhr, welche gestoppt ist (d.h. die Zeiger bewegen sich nicht mit der Zeit). Keiner der Gefangenen weiß, zu welcher Stunde die Uhr gestoppt wurde. Ab und zu, darf ein Gefangener den Raum betreten und MUSS den Stundenzeiger genau 3 Stunden verstellen (entweder vor oder zurück).
Die Reihenfolge in welcher die Gefangenen in den Raum gerufen werden ist vorgegeben, aber nur dem Gefängnisverwalter bekannt. Dieser garantiert jedoch, dass jeder Gefangene „unendlich oft“ aufgerufen wird (d.h. für jeden Gefangenen und jede natürliche Zahl N, gibt es einen Zeitpunkt, an dem der Gefangene zumindest N mal im Raum war).
Zu jedem Zeitpunkt ist es jedem einzelnen der Gefangenen erlaubt zum Gefängnisverwalter zu gehen und zu behaupten „Jeder Mann war bereits im Raum“. Wenn die Aussage stimmt, kommen alle frei. Andernfalls werden alle erschossen (wieso sind Rätsel eigentlich immer so dramatisch? *G*).
Den Gefangenen ist es erlaubt sich vor dem Spiel zu beraten um eine Strategie zu entwerfen. Danach ist jede Kommunikation zwischen ihnen verboten.
Zeige eine Strategie, die keinem Gefangenen das Leben kostet (d.h. kein Gefangener wird jemals behaupten, dass alle im Raum waren, wenn das nicht der Fall war) und welche die Gefangenen irgendwann freibekommt, egal in welcher Reihenfolge sie aufgerufen werden (nimm an, dass sie unendlich oft aufgerufen werden).

Wenn das so weitergeht, lösen wir wirklich alle schönen Rätsel die Yoni da zusammengetragen hat :wink:.

MfG
Greenberet

Original auf http://www.technion.ac.il/~yonie/riddles.html

#2

Kleiner Tipp
Hallo!

Wenn sie nicht wissen, zu welcher Zeit die Uhr gestoppt wurde, nützt ihnen die Uhr nichts. Das müssen sie also erstmal alle wissen. Für die ersten 100 Tage (oder länger) vereinbaren sie, dass an jedem ungeraden Tag die Zeiger vorgestellt werden und an jedem geraden Tag zurück. Dann weiß es (fast) jeder.

Grüße

Andreas

#3

Fragen/Einwände
Hi,

ich grübele schon eine Weile über diesem Rätsel, aber ich sehe nicht, wie mit der Uhr genügend Informationen vermittelt werden können. Es gibt doch nur 4 verschiedene Zustände/Zeiten, die ein Gefangener sehen kann, wenn er den Raum betritt, oder?

Für die ersten 100 Tage (oder länger) vereinbaren sie,
dass an jedem ungeraden Tag die Zeiger vorgestellt werden und
an jedem geraden Tag zurück. Dann weiß es (fast) jeder.

Was ist, wenn erst nach 101 Tagen der erste Besuch des Raumes stattfindet? Dann weiß es keiner.

Was ist mit dem zweiten, dritten, vierten Besucher am selben Tag? Die sehen alle unterschiedliche Zeiten.

Andreas

#4

Hallo Andreas!

ich grübele schon eine Weile über diesem Rätsel

Ich wünschte, so viel Zeit hätte ich auch über.

Es gibt doch nur 4 verschiedene
Zustände/Zeiten, die ein Gefangener sehen kann, wenn er den
Raum betritt, oder?

Ja. Das sind 2 Bit. Bei einer Glühbirne mit Schalter wäre es 1 Bit, und dazu gibt es auch ein Rätsel mit Lösung.

Was ist, wenn erst nach 101 Tagen der erste Besuch des Raumes
stattfindet? Dann weiß es keiner.

Dann nehmen wir eben 1000 Tage. Wer es dann noch nicht weiß, enthält sich der Stimme.

Was ist mit dem zweiten, dritten, vierten Besucher am selben
Tag?

Ich dachte, da steht: „Jeden Tag einer.“ Oder?

Nachles…

Ups! Das steht da ja gar nicht.

Wie komme ich denn da drauf?

Kopfkratz…

Grüße

Andreas

#5

Guten Tag,

Es gibt doch nur 4 verschiedene
Zustände/Zeiten, die ein Gefangener sehen kann, wenn er den
Raum betritt, oder?

Ja. Das sind 2 Bit. Bei einer Glühbirne mit Schalter wäre es 1
Bit, und dazu gibt es auch ein Rätsel mit Lösung.

Ich habs mir immer als Zähler modulo 4 vorgestellt, wobei jeder Gefangene die Operationen +1 oder -1 ausführen darf.

Was ist, wenn erst nach 101 Tagen der erste Besuch des Raumes
stattfindet? Dann weiß es keiner.

Seh ich genauso. Wir können kein N angeben bis zu dem mindestens ein Gefangener im Raum war.

Also ich hab verzweifelt versucht irgendeine Invariante für 100 Ein-Bit-Variablen in einem modulo-4-Zähler zu finden, aber irgendwie komm ich nicht weiter…
Primzahlen, Zweierpotenzen, Huffman-Codes,… führt bei mir alles zu nix.

Brutales Rätsel…

MfG
Beret

#6

[Teilspoiler] Re: Kleiner Tipp

Hallo!

Wenn sie nicht wissen, zu welcher Zeit die Uhr gestoppt wurde,
nützt ihnen die Uhr nichts.

Falsche Annahme.

MfG
Benjamin

PS: Als Rätselnsteller hab ich mich verpflichtet gefühlt die Lösung im Netz zu finden, damit ich Fragen beantworten und Tipps geben kann. Nachdem ich über das Rätsel sporadisch seit einer Woche nachgedacht habe und nicht weitergekommen bin, wär ich sowieso nicht mehr draufgekommen…

#7

Lösung?
Hallo!

Ich bin mir nicht sicher, aber ich habe so eine Idee, vielleicht nicht die beste, es dauert auch sehr lange, aber es könnte funktionieren. Vielleicht.

Die ersten drei Monate oder meinetwegen drei Jahre nutzen sie dazu, festzustellen, wann die Uhr gestoppt wurde. Innerhalb dieser Zeit wird wohl jeder einmal drin gewesen sein. Wenn die Uhr auf einer geraden Zahl steht, dreht jeder sie um drei Stunden vor. Steht sie auf einer ungeraden, dreht jeder sie um drei Stunden zurück. Wenn einer reinkommt, und die Uhr steht auf 12, dann weiß er: Die Uhr wurde um 12 oder um 3 Uhr gestoppt.

Diese Zeitspanne, von 12 bis 3 Uhr, nenne ich „Null“. Den Bereich zwischen 6 und 9 Uhr nenne ich „Eins“

Einer wird als Zähler bestimmt.

Wenn einer reinkommt, der noch nicht gezählt wurde, und die Uhr steht auf „Null“ stellt er sie auf „Eins“. Jeder weitere, der reinkommt, lässt sie auf „Eins“.

Wenn der Zähler reinkommt, und die Uhr steht auf „Eins“, zählt er eins hoch und stellt die Uhr wieder auf „Null“.

Sobald er bis 100 gezählt hat, reibt er sich die Hände…

Grüße

Andreas

#8

Muss der Gefangene die Uhr verstellen?

Wenn ja, dann hätte das Rätsel den gleichen Lösungsgang, wie wenn jeder 1 Stunde verstellen müsste.

Dann geht es nur um Schaltstellungen Plus, Minus.

Nur eine Zahl, die jeder kennen muss wäre anders.

Geht das in die richtige Richtung?

#9

Hallo

Ich hab die Lösung.

Die Gefangenen entwickeln ein System, wo alle nie behaupten können, dass schon alle zumindest einmal bei der Uhr waren, wenn noch einer fehlt.
Fett: Wenn noch einer fehlt!!

#10

Hallo Andreas,

die Grundidee ist super! Ich würde folgende Modifikationen vornehmen:

Die ersten drei Monate oder meinetwegen drei Jahre nutzen sie
dazu, festzustellen, wann die Uhr gestoppt wurde. Innerhalb
dieser Zeit wird wohl jeder einmal drin gewesen sein.

Geht nicht; wir können für keine Zeitspanne, die wir vorab festlegen, garantieren, dass überhaupt jemand im Raum gewesen ist. Aber es ist auch egal, wann die Uhr gestoppt wurde.

Diese Zeitspanne, von 12 bis 3 Uhr, nenne ich „Null“. Den
Bereich zwischen 6 und 9 Uhr nenne ich „Eins“

Wir teilen die Uhr einfach in zwei zusammenhängende 6-Stunden-Bereiche „Null“ und „Eins“. Wie wir das festlegen, ist egal; wichtig ist, dass jeder Gefangene die gleiche Zuordnung der Uhrzeiten zu den zwei Bereichen kennt. (Also meinetwegen: Stundenzeiger links (oder auf 12) => „Null“, Stundenzeiger rechts (oder auf 6) => „Eins“.)

Wichtige Eigenschaft: Jede Gefangene kann, egal welche Uhrzeit er vorfindet, entweder durch einen Zug den Zustand (Null/Eins) belassen oder durch den anderen Zug den Zustand ändern.

Einer wird als Zähler bestimmt.

Wenn einer reinkommt, der noch nicht gezählt wurde, und die
Uhr steht auf „Null“ stellt er sie auf „Eins“. Jeder weitere,
der reinkommt, lässt sie auf „Eins“.

Wenn der Zähler reinkommt, und die Uhr steht auf „Eins“, zählt
er eins hoch und stellt die Uhr wieder auf „Null“.

Sobald er bis 100 gezählt hat, reibt er sich die Hände…

Genau so machen wir es dann.

Andreas

#11

Hallo Andreas!

die Grundidee ist super!

Danke! Das freut mich sehr.

Ich würde folgende Modifikationen
vornehmen:…

Das ist super! So sparen sie eine Menge Zeit, und sicherer ist es auch.

Grüße

Andreas

#12

Korrekt [owT]
[owT]=ohne weiteren Text

#13

Hallo,

so ganz habe ich das noch nicht verstanden. Wie kann der Zähler die beiden folgenden Fälle auseinanderhalten:

  1. Der Zähler geht als erstes rein und die Uhr steht auf 1
  2. Ein Nichtzähler geht als erstes rein, sieht die Uhr auf 0 und stellt sie auf 1. Der Zähler geht als zweites rein.

In 2) zählt der Zähler richtig. Bei 1) zählt er eine Person zuviel, das ist dann für ihn tödlich. Oder habe ich da einen Denkfehler? Es reicht doch auch aus, das Problem für zwei Personen zu betrachten, da gibt es dann den Ansagefehler.

Viele Grüße
Diether

#14

Hallo Diether,

Wie kann der Zähler die beiden folgenden Fälle auseinanderhalten:

  1. Der Zähler geht als erstes rein und die Uhr steht auf 1
  2. Ein Nichtzähler geht als erstes rein, sieht die Uhr auf 0
    und stellt sie auf 1. Der Zähler geht als zweites rein.

du hast recht; das ist ein Problem. Aber es ist behebbar:

Die Gefangenen könnten sich darauf einigen, jede Person zweimal zu zählen. Jeder Nicht-Zähler stellt also zweimal die Uhr von 0 auf 1; der Zähler zählt bis 198 und verkündet dann, dass alle im Raum waren.

Fall 2: Er hat richtig gezählt, dann waren 99 Nicht-Zähler je (mindestens) zweimal im Raum.

Fall 1: Er hat falsch gezählt: Es gab tatsächlich nur 197 Besuche, bei denen die Uhr von 0 auf 1 gestellt wurde. Trotzdem muss jeder der 99 Nichtzähler im Raum gewesen sein, allerdings wurde einer von ihnen nur einmal gezählt.

Andreas

#15

Moin!

Einer wird als Zähler bestimmt.

Wenn der keine Sonderrechte hat (kann den Raum jederzeit betreten), bringt das nichts. Davon steht aber nichts in der Aufgabenstellung.

Genießt niemand Sonderrechte, wird im Schnitt jeder einmal eine 1 und dann nur noch Nullen sehen. Ohne, daß Sonderrechte hat, dürfte die Aufgabe m. E. nicht zu lösen sein.

Munter bleiben… TRICHTEX

#16

Hi Andreas,

Ja. Das sind 2 Bit. Bei einer Glühbirne mit Schalter wäre es 1
Bit, und dazu gibt es auch ein Rätsel mit Lösung.

Kann mich täuschen (lange her), aber soweit ich war dort kein
Zwang den Schalterzustand jedes Mal zu ändern.

LG Alex

#17

Hi Alexander!

Das stimmt.

Grüße

Andreas