Häftlinge entlassen oder hinrichten

[Biene88]

Hallo zusammen

Ich habe in einer Vorlesung folgendes Rätsel gestellt bekommen:

Eine beliebige Menge Häftlinge sitzen im Gefängnis.
Jeder Häftling hat entweder eine schwarze oder eine weiße Kugel auf dem Dach seiner Zelle. Die Häftlinge können die eigene Kugel aber nicht sehen, wohl aber die aller anderen. Kommunikation ist nicht möglich.
Jeden Morgen hat jeder Häftling die Möglichkeit, auf das Kommando eines Wärters einen Knopf zu drücken. Wenn dann alle Häftlinge mit einer weißen Kugel auf der Zelle den Knopf drücken, die mit einer schwarzen Kugel jedoch nicht, werden alle freigelassen.
Wenn einer von den Häftlingen falsch drückt – also wenn einer mit einer schwarzen Kugel auf der Zelle drückt, oder einer mit einer weißen Kugel auf der Zelle nicht drückt – dann werden alle hingerichtet. Wenn keiner der Häftlinge drückt, bleibt alles beim alten, alle bleiben im Gefängnis und haben jeden Tag dieselbe Chance.
Vorausgesetzt alle Häftlinge sind genauso schlau wie Sie, wie entscheiden Sie sich, wenn der Wärter morgens Ihnen die Möglichkeit gibt den Knopf zu drücken?
Begründen Sie Ihre Antwort.

Tipp zu diesem Rätsel war lediglich "vollständige Induktion".
Natürlich habe ich nach diesem Rätsel bereits gegoogelt und viele ähnliche gefunden, allerdings waren da die Voraussetzungen meistens anders. So gibt es ein ähnliches Rätsel mit Kannibalen und 4 Gefangenen, die jeweils 2 schwarze und 2 weiße Hüte tragen. Diese dürfen aber kommunizieren bzw. sehen jeweils den Vodermann und kennen die Anzahl der Hüte und Farben.
Leider kenne ich nicht die Anzahl der Häftlinge, auch nicht die Anzahl der Kugeln und kommunizieren dürfen die Häftlinge auch nicht.
Deshalb hoffe ich das sich hier ein Knobel-Profi findet, der mir helfen kann

LG
Biene

[Cujo]

Hallo Biene



Guck mal hier Der neue Gefängnisdirektor

Ich denke, das müsste das gleiche Rätsel sein

[Biene88]

Hallo Cujo,

stimmt, das Rätsel ist ähnlich und ich verstehe den Lösungsweg, allerdings habe ich nicht nur mit der Anzahl der Kugeln zu kämpfen, sondern auch mit der Zweifarbigkeit. Die Kugeln ändern sich nicht täglich und es liegen definitv auf jeder Zelle Kugeln. Natürlich ist es möglich, dass nur eine Zelle eine weiße Kugel hat und die anderen alle schwarze, doch wie soll ich dann ohne Kommunikation herausfinden, das ich eine weiße Kugel habe? Weil die Anzahl, wieviele Kugeln einer Farbe verteilt wurden, ist ja nicht gegeben.

Zusatz: Stimmt gar nicht, was ich geschrieben habe. Durch den Satz "Jeder Häftling hat entweder eine schwarze oder eine weiße Kugel auf dem Dach seiner Zelle" kann ich davon ausgehen, das von jeder Farbe eine Kugel mindestens da sein muss. Sitze ich also in einer Zelle und sehe nur schwarze Kugeln, kann ich davon ausgehen eine weiße zu haben und sollte den Knopf drücken. Umgekehrt heißt das, sehe ich nur weiße dann habe ich definitv eine schwarze Kugel und sollte nicht drücken.
Allerdings weiß ich dann immernoch nicht, wie ich meine Farbe errate, wenn die beiden Farben verschieden häufig vorhanden sind.

[Friedel]

Durch die Aufagbenstellung ist nur festgelgt, dass jeder Häftling genau eine Kugel hat, die entweder weiß oder schwarz ist. Es könnten auch alle Häftlinge weiße Kugen haben. Da am ersten Tag keiner weiß welche Farbe er hat, drückt keiner. Das sind alle Häftlinge mit einer weißen Kugel, wenn alle Häftlinge schwarze Kugen haben! Wenn danach nicht alle Häftlinge frei gelassen werden, wissen sie alle, dass es mindestens 1 weiße Kugel geben muss. Wer keine weiße Kugel sieht, muss also am nächsten Tag drücken. Wenn wieder keiner drückt, wissen alle, dass keiner keine weiße Kugel gesehen hat. Es müssen also mindestens 2 weiße Kugeln sein. Am nächsten Tag drücken alle, die nur eine weiße Kugel sehen…

Wenn einer von den Häftlingen falsch drückt – also wenn einer mit einer schwarzen Kugel auf der Zelle drückt, oder einer mit einer weißen Kugel auf der Zelle nicht drückt – dann werden alle hingerichtet.

Nach dieser Regel müssten eigentlich alle Häftlinge mit weioßen Kugeln schon am ersten Tag drücken. Dieses Problem ist in dieser Aufgabe imho sehr schon durch

Wenn keiner der Häftlinge drückt, bleibt alles beim alten, alle bleiben im Gefängnis und haben jeden Tag dieselbe Chance.

umgangen.

[Biene88]

Das ist logisch, vielen Dank

[Biene88]

Wobei eine Frage stellt sich mir da noch: Das heißt es kann auch mehr als zwei weiße Kugeln geben und für jede weiße Kugel kommt dann ein Tag hinzu?

[Friedel]

Genau so isses. Im ungünstigsten Fall haben alle Häftlinge weiße Kugeln. Dann dauert es so viele Tage wie es Häftlinge sind, bis sie alle frei kommen.