Rechenaufgaben

[Cybermancer]

Ich hab am WE ein kleines feines Rätsel gehört:

100 Gefangene haben am Ostersonntag die Chance auf Freiheit.
Jeder Gefangene bekommt eine eindeutige Nummer zwischen 1 und 100 zugeteilt.
Der erste Gefangene geht dann alleine durch eine Tür in einen Raum mit einem Kasten
mit 100 Schubladen in denen wiederum die Zahlen von 1-100 zufällig verteilt sind.
Der Gefangene darf 50 Schubladen öffnen.
Ist darunter seine eigene Nummer, darf er in den nächsten Raum,
wenn nicht, ist das Spiel vorbei und keiner kommt frei.

Also nur wenn alle 100 Gefangenen ihre eigene Zahl gezogen haben, sind alle frei, sonst keiner.

Mit welcher Strategie (die sie vorher verabreden dürfen) ist ihre Chance auf Freiheit am höchsten?

Kleiner Hinweis:
Die Faktultät von oben könnte dabei eine Rolle spielen.

Werden die Fächer wieder geschlossen?

[Cybermancer]

Ich hab am WE ein kleines feines Rätsel gehört:

100 Gefangene haben am Ostersonntag die Chance auf Freiheit.
Jeder Gefangene bekommt eine eindeutige Nummer zwischen 1 und 100 zugeteilt.
Der erste Gefangene geht dann alleine durch eine Tür in einen Raum mit einem Kasten
mit 100 Schubladen in denen wiederum die Zahlen von 1-100 zufällig verteilt sind.
Der Gefangene darf 50 Schubladen öffnen.
Ist darunter seine eigene Nummer, darf er in den nächsten Raum,
wenn nicht, ist das Spiel vorbei und keiner kommt frei.

Also nur wenn alle 100 Gefangenen ihre eigene Zahl gezogen haben, sind alle frei, sonst keiner.

Mit welcher Strategie (die sie vorher verabreden dürfen) ist ihre Chance auf Freiheit am höchsten?

Kleiner Hinweis:
Die Faktultät von oben könnte dabei eine Rolle spielen.

Spoiler

https://www.cl.cam.ac.uk/~gw104/Locker_Puzzle.pdf

[giffi marauder]

Ich hab am WE ein kleines feines Rätsel gehört:

100 Gefangene haben am Ostersonntag die Chance auf Freiheit.
Jeder Gefangene bekommt eine eindeutige Nummer zwischen 1 und 100 zugeteilt.
Der erste Gefangene geht dann alleine durch eine Tür in einen Raum mit einem Kasten
mit 100 Schubladen in denen wiederum die Zahlen von 1-100 zufällig verteilt sind.
Der Gefangene darf 50 Schubladen öffnen.
Ist darunter seine eigene Nummer, darf er in den nächsten Raum,
wenn nicht, ist das Spiel vorbei und keiner kommt frei.

Also nur wenn alle 100 Gefangenen ihre eigene Zahl gezogen haben, sind alle frei, sonst keiner.

Mit welcher Strategie (die sie vorher verabreden dürfen) ist ihre Chance auf Freiheit am höchsten?

Kleiner Hinweis:
Die Faktultät von oben könnte dabei eine Rolle spielen.

Hier ein anschauliches Video dazu.

[Eisrose]

Mal eine neue Aufgabe, die ich ebenfalls beeindruckend fand:

Zehn Leute stehen hintereinander und haben einen Hut auf. Jeder der Hüte hat ein Hutband, welches der Träger des Hutes nicht sehen kann. Das Hutband kann schwarz oder weiss sein. Jetzt muss jeder Hutträger die Farbe seines Hutbandes raten. Bei insgesamt keinem oder maximal einem einzigen Fehler überleben alle, ab zwei Fehlern werden alle getötet. Also maximal ein Fehlrateversuch ist erlaubt.

Hinweis: der Letzte kann alle anderen sehen, also alle übrigen neun Hüte. Der Vorletzte kann die restlichen acht sehen und so weiter... Die Ratereihenfolge können die Hutträger festlegen. Jeder darf aber nur schwarz oder weiss sagen, sonst nichts, auch keine sonstigen Zeichen. Nur die Strategie dürfen sie vorher absprechen.

Mit der richtigen Strategie ist das Überleben zu 100 Prozent sicher! Wie lautet die Strategie?

Falls jemand gar keine Idee hat, die Strategie schon mal im Spoiler. Aber selbst, wenn man die Lösung kennt, muss man noch einen Moment drüber nachdenken, lach.

Spoiler

Die Lösung ist: der letzte Hutträger, der alle anderen sehen kann, ist natürlich als erster dran und zählt einfach alle schwarzen Hutbänder. Ist die Zahl gerade, sagt er weiss, ist die Zahl ungerade, sagt er schwarz. Das wäre dann auch der eine eventuelle Fehlversuch. Mit dieser Info können aber alle anderen ihre richtige Hutbandfarbe nennen.

[giffi marauder]

Mal eine neue Aufgabe, die ich ebenfalls beeindruckend fand:

Zehn Leute stehen hintereinander und haben einen Hut auf. Jeder der Hüte hat ein Hutband, welches der Träger des Hutes nicht sehen kann. Das Hutband kann schwarz oder weiss sein. Jetzt muss jeder Hutträger die Farbe seines Hutbandes raten. Bei insgesamt keinem oder maximal einem einzigen Fehler überleben alle, ab zwei Fehlern werden alle getötet. Also maximal ein Fehlrateversuch ist erlaubt.

Hinweis: der Letzte kann alle anderen sehen, also alle übrigen neun Hüte. Der Vorletzte kann die restlichen acht sehen und so weiter... Die Ratereihenfolge können die Hutträger festlegen. Jeder darf aber nur schwarz oder weiss sagen, sonst nichts, auch keine sonstigen Zeichen. Nur die Strategie dürfen sie vorher absprechen.

Mit der richtigen Strategie ist das Überleben zu 100 Prozent sicher! Wie lautet die Strategie?

Falls jemand gar keine Idee hat, die Strategie schon mal im Spoiler. Aber selbst, wenn man die Lösung kennt, muss man noch einen Moment drüber nachdenken, lach.

Ich versuch mal einen Spontanansatz:

Spoiler

Schwarz/weiss ist so was wie ein binärer Code.
Der Letzte sieht (bis auf sein eigenes Bit) alle vor ihm.
Alles was er aber sagen darf ist ebenfalls schwarz oder weiß.
Da ein Fehlversuch gestattet ist, nehme ich an, das dass die erste Antwort des letzten in der Reihe ist.
Der Rest muss dann jedenfalls richtig antworten.

Beginnt der letzte, der am meisten sieht, haben alle die Information über die (möglicherweise falsche Anzahl von schwarzen Hüte) hinter und
(richtige) vor sich.

Ev. geht die Lösung in Richtung gerade/ungerade Anzahl (Parity) von schwarzen Hüten.
Sieht der hintere also eine ungerade Anzahl von schwarzen Hüten, nimmt er einfach mal an,
seiner ist schwarz, damit die Zahl gerade wird.
Er sagt also "schwarz".
Der Vorletzte weiss nun, dass die Anzahl der schwarzen Hüte inkl. dem Letzen (der möglischerweise auch falsch ist) gerade ist.
Damit weiss er auch, dass der hinter ihm eine ungerade Anzahl sieht.
Sieht er selbst vor sich eine gerade Anzahl, so muss sein Hut schwarz sein, sonst weiss.
Auch er macht somit nichts anderers als die Anzahl der schwarzen Hüte (die hinter ihm, die schon geantwortet haben
und die vor ihm die er sehen kann) auf gerade zu ändern (schwarz) oder gerade zu lassen (weiss).
Ich gehe jetzt einfach davon aus, dass wenn das jeder macht, maximal der Hinterste falsch liegt,
da dieser ja nicht wissen kann, ob die Anzahl nun tatsächlich gerade oder ungerade ist.
Ist sie gerade, liegt er richtig.
Ist sie ungerade, liegt er zwar falsch, die Anzahl der restlichen schwarzen Hüte ist dann aber wieder gerade.

Test:
(Alle blicken nach rechts)
Ist (Anzahl gerade)
s,s,w,w,w,s,w,s,s,s,w
Antworten:
s (5+0, 5 schwarzen vor ihm, keiner hinter ihm)
s (4+1, 4 schwarzen vor ihm und 1 hinter ihm)
w (4+2)
w (4+2)
w (4+2)
s (3+2)
w (3+3)
s (2+3)
s (1+4)
s (5)
w (6)

Ist (Anzahl ungerade)
w,s,w,w,w,s,w,s,s,s,w
Antworten:
s (5+0, 5 schwarzen vor ihm, keiner hinter ihm) (das ist falsch)
s (4+1, 4 schwarzen vor ihm und 1 hinter ihm)
w (4+2)
...
w (6)

Spoiler

Die Lösung ist: der letzte Hutträger, der alle anderen sehen kann, ist natürlich als erster dran und zählt einfach alle schwarzen Hutbänder. Ist die Zahl gerade, sagt er weiss, ist die Zahl ungerade, sagt er schwarz. Das wäre dann auch der eine eventuelle Fehlversuch. Mit dieser Info können aber alle anderen ihre richtige Hutbandfarbe nennen.

Warum das funktioniert ist auch schnell klar:
Ist den Spielern die Parität (garde oder ungerade) bekannt, kommen sowieso alle drauf,
weil sie die Anzahl der schwarzen Hüte vor und hinter sich kennen und somit auf die eigene Farbe schließen können.
Ist die Parität jedoch unbekannt, dann stimmt entweder die (gemeinsame) Annahme und alle liegen richtig,
oder der erste liegt falsch, korrigiert aber den "Fehler" und für alle anderen stimmts dann wieder.
Sie müssen sich vorher nur drauf einigen, ob sie gerade oder ungerade annehmen.

[Eisrose]

Ich versuch mal einen Spontanansatz:

Ui, ui, ui. Du hast die Strategie selber rausbekommen? Alle Achtung! Hab ich nicht geschafft und brauchte sogar noch einen Moment, bis ichs verstand, als ich den Lösungsansatz kannte, lach.

[giffi marauder]

Ich versuch mal einen Spontanansatz:

Ui, ui, ui. Du hast die Strategie selber rausbekommen? Alle Achtung! Hab ich nicht geschafft und brauchte sogar noch einen Moment, bis ichs verstand, als ich den Lösungsansatz kannte, lach.

Nun ja, mit nunmehr 45 Jahren Konsum diverser mathematischer Rätselbücher,
ist es ein bisschen schwierig noch zweifelsfrei zu wissen, ob einem nicht das eine oder andere Rätsel
schon mal durch den Kopf ging.
Aber nachgesehen hab ich da jetzt niergends.