Der neue Gefängnisdirektor

[Cujo]

An seinem ersten Tag stellt der neue Gefängnisdirektor 10 Häftlingen, die sich laut seiner Akten besonders gut geführt haben, die Freiheit in Aussicht. Zuvor müssen sie allerdings noch eine Aufgabe erfolgreich lösen.

Die 10 Häftlinge kommen in einen runden Gebäudekomplex mit 10 Zellen. Jeder Häftling kommt in eine Zelle. Die Zellen sind absolut schallisoliert und die Zelltüren sind so dicht, dass kein Gefangener die anderen Zellen sehen kann. Zu Beginn der Aufgabe malt ein Wärter einen Punkt über eine unbestimmte Anzahl von Zelltüren (mindestens über 1 Zelltür).

Einmal am Tag werden für kurze Zeit alle Zelltüren gleichzeitig geöffnet. Dann sollen alle Häftlinge heraustreten, die einen Punkt über ihrer Zelltür haben. Die Häftlinge können, wenn die Tür geöffnet ist, die Zelltüren der anderen Häftlinge sehen, wissen aber selbst nicht, ob über ihrer Zelltür ein Punkt ist oder nicht. Jegliche Kommunikation zwischen den Häftlingen ist strengstens verboten.

Tritt ein Häftling heraus, der keinen Punkt hat oder bleibt einer drinnen, der einen hat, haben die Häftlinge die Aufgabe nicht gelöst und müssen ihre volle Haftstrafe absitzen.

Wie sollten die Häftlinge am besten vorgehen, um frei gelassen zu werden?

[Friedel]

Hallo.
Eine sehr schöne, wenn auch nicht neue Aufgabe - zumindest ist die übliche Fassung der Aufgabe imho sehr schön. Die Beschränkung auf 10 Häftlinge und Zellen macht sie allerdings imho weniger interessant. In den meisten Variationen dieser Aufgabe liegen die Zahlen bei mindestens 100.

Mehr ->

Wenn die Zelltüren geöffnet werden, zählt jeder Häftling von den Zelltüren die er sehen kann, diejenigen, die einen Punkt haben. Zu der Zahl zählt er eins dazu. Das Ergebnis nennt die Zahl des Tages, an dem er vor die Tür treten muss.

Annahme 1: Über genau einer Tür ist ein Punkt.
Wenn ein Häftling keinen Punkt sehen kann, zählt er also 0 Punkte. Eins zählt er dazu. Er muss also gleich am Ersten Tag vor die Tür treten. Wenn er keinen Punkt sehen kann, muss er selbst ja einen Punkt haben, denn ein Punkt wurde ja mindestens vergeben. Alle anderen sehen einen Punkt. Sie rechnen sich also aus, dass sie am zweiten Tag vor die Tür treten müssten, wenn sie da nicht schon frei wären.

Annahme 2: Über 2 Türen ist ein Punkt.
Wer selbst einen Punkt hat, sieht jetzt einen Punkt, die anderen sehen 2 Punkte. Wenn es nur einen Punkt gäbe, müsste der entsprechende Häftling (wie eben beschrieben) am ersten Tag vor die Tür treten. Da der Häftling am ersten Tag in der Zelle bleibt, muss er auch einen Punkt sehen. Die beiden bepunkteten können also am 2. Tag erkennen, dass sie selbst einen Punkt haben und treten dann vor sie Tür. Die anderen sehen ja 2 Punkte, würden also erst am dritten Tag vor die Tür treten - wenn sie da nicht schon frei wären.

Usw.

Zusatzaufgabe:
Diese Variante hat mich auf eine Idee gebracht, mit der das ganze auch lösbar wird, wenn nicht vorgegeben ist, dass mindestens ein Punkt vergeben wurde. Dazu müssen die Häftlinge aber vor dem Experiment absprechen dürfen um eine Strategie zu vereinbaren. Hat jemand eine Idee, wie die Strategie aussehen könnte?

[black]

Mehr ->

Einmal am Tag werden für kurze Zeit alle Zelltüren gleichzeitig geöffnet. Dann sollen alle Häftlinge heraustreten, die einen Punkt über ihrer Zelltür haben. ...
Tritt ein Häftling heraus, der keinen Punkt hat oder bleibt einer drinnen, der einen hat, haben die Häftlinge die Aufgabe nicht gelöst und müssen ihre volle Haftstrafe absitzen.

Müssen damit nicht alle Häftlinge schon am ersten Tag richtig liegen?

[Cujo]

@black Hast recht, ich habe den Aufgabentext geändert. Danke für den Hinweis

[Friedel]

Stimmt. Man muss das eigentlich so interpretieren, wie black es gemacht hat. Aber die jetzt geänderte Fassung ist imho auch nicht 100%-ig. Es sollten schon alle Häftlinge mit Punkt am selben Tag vor die Tür treten.

[Cujo]

So, ich löse dann mal auf.

Friedels Lösung ist natürlich zu 100 % richtig

Ich setze den Haken aber noch nicht, da Friedel ja noch eine Zusatzaufgabe gestellt hat

Zusatzaufgabe:
Diese Variante hat mich auf eine Idee gebracht, mit der das ganze auch lösbar wird, wenn nicht vorgegeben ist, dass mindestens ein Punkt vergeben wurde. Dazu müssen die Häftlinge aber vor dem Experiment absprechen dürfen um eine Strategie zu vereinbaren. Hat jemand eine Idee, wie die Strategie aussehen könnte?

[black]

Vor allem hinsichtlich der Zusatzaufgabe stellt sich mir folgende Fragen:

Falls die Aufgabe richtig gelöst wurde, werden alle 10 frei gelassen, oder?
Wann genau ist die Aufgabe erfolgreich gelöst?
Müssen alle Häftlinge mit Punkt am selben Tag raus treten?
Müssen die ohne Punkt am Ende wissen, dass sie keinen haben? (Falls ja, wie teilen sie dies dem Direktor mit?)

[Friedel]

Da die Zusatzaufgabe von mir ist, antworte ich mal.

Vor allem hinsichtlich der Zusatzaufgabe stellt sich mir folgende Fragen:
Falls die Aufgabe richtig gelöst wurde, werden alle 10 frei gelassen, oder?

Richtig. Und zwar sofort.

Wann genau ist die Aufgabe erfolgreich gelöst?
Müssen alle Häftlinge mit Punkt am selben Tag raus treten?
Müssen die ohne Punkt am Ende wissen, dass sie keinen haben? (Falls ja, wie teilen sie dies dem Direktor mit?)

An einem Tag treten die Häftlinge, die einen Punkt haben, vor die Tür. Alle anderen bleiben drin. Die Tür ist ja nicht lange offen. Wenn sie zu gemacht wird, und genau die Häftlinge draußen sind, die einen Punkt haben, ist die Aufgabe gelöst. Wenn die Aufgabe nicht gelöst ist und keiner vor die Tür getreten ist, besteht am nächsten Tag wieder die Möglichkeit, die Aufgabe zu lösen. In allen anderen Fällen (wenn mindestens ein Häftling vor die Tür getreten ist, aber mindestens ein Häftling vor die Tür getreten ist, der keinen Punkt hat oder mindestens ein Häftling in der Zelle geblieben ist, der einen Punkt hat) ist die Chance auf vorzeitige Freiheit vertan.

[black]

Mehr ->

An einem Tag treten die Häftlinge, die einen Punkt haben, vor die Tür. Alle anderen bleiben drin. Die Tür ist ja nicht lange offen. Wenn sie zu gemacht wird, und genau die Häftlinge draußen sind, die einen Punkt haben, ist die Aufgabe gelöst.

Dann bedarf es aber m.E. für die Zusatzaufgabe auch keiner Absprachen:

Am 1. Tag bleiben einfach alle drin. (Es kann sich ja auch keiner sicher sein.)
Hat keiner einen Punkt, ist die Aufgabe damit am 1. Tag gelöst.
Ist sie es nicht, können sie ab dem 2. Tag analog zur ursprünglichen Lösung verfahren.

[Friedel]

Richtig. So einfach geht das. Die Vereinbarung, dass mindestens 1 Gefangener einen Punkt hat, verändert den Tag, an dem die Gefangenen heraustreten. Aber sie verändert nicht den Lösungsweg.