Der Gefängnisdirektor hat Langeweile

[Friedel]

Das ist bei weitem nicht der ungünstigste Fall. Es könnten maximal 25 "Kreisläufe" sein.

Ich sehe mach wie vor nicht, wie man sich dem Problem nähern könnte. Es ist imho völlig egal welche Fächer die Häftlinge öffnen, es muss nur vorher abgesprochen sein. Der Pfarrer kann bei den ersten 2 Häftlingen dafür sorgen, dass sie ihre Ausweise finden. Alle anderen haben einen Chance von jeweils genau 50%, dass sie ihre Ausweise finden. Welche Fächer der erste Häftling öffnet, kann die folgenden Häftlinge nicht beeinflussen, denn sie erfahren ja nicht, welche Fächer er geöffnet hat.

[Kolabord]

Wenn aber alle ihre Fächer nach einem System öffnen, dann wären die Erfolge stark von einander Abhängig und zwar so stark, dass auch ohne den Pfarrer mit hohere Wahrscheinlichkeit ihr Fach finden. Mit Pfarrer lässt es sich dann auf jeden Fall lösen. Jetzt gilt es ein solches System zu finden, zumindest, wenn ich alles richtig verstanden habe.

[Otmar]

Hallo zusammen,
@Friedel

Mehr ->

Das ist bei weitem nicht der ungünstigste Fall. Es könnten maximal 25 "Kreisläufe" sein.

25 Kreisläufe geht in Richtung des anderen Extrems. Wenn du davon ausgehst, dass ein Kreislauf mehr als ein Fach haben muss, dann ist dieses andere extem tatsächlich 25 Kreisläufe mit je 2 Fächern. Die Frage ist, ob diese Situation ungünstig wäre, wenn du darauf die von Kolabord angegeben Strategie anwendest. Würden wir auch Kreisläufe mit einem Fach als Kreislauf bezeichnen, dann kann es davon maximal 50 geben. Bei 50 solchen Kreisläufen wird jeder Gefangene bei der ersten Tür fündig. Das ist aus Sicht der Gefangenen die günstigste Situation.

@Kolabord
hab da noch ein paar

Mehr ->

Jetzt gilt es ein solches System zu finden, zumindest, wenn ich alles richtig verstanden habe.

Das System mit dem die Gefangenen die Fächer öffenen, hast du doch schon gefunden. Da kommt nichts mehr hinzu! Mit dieser Strategie, werden die Gefangenen mit relativ hoher Wahrscheinlichkeit auch ohne Pfarrer freikommen. (Auch wenn wir die Zahl der Gefangenen beliebig erhöhen, mit deiner Strategie kommen sie mit einer Wahrscheinlichkeit, die größer als 1-ln(2) ist, frei, wenn wenigstens die Hälfte aller Fächer geöffnet werden dürfen. Nach der Lösung poste ich noch einen Link zu einer Seite in der die Berechnung dazu steht.)
Um die nötige Aktion des Pfarrers zu finden und ob er überhaupt was tun muss, solltest du dir nochmal die Kreisläufe auschauen. Für die Untersuchung erlaubst du vorerst (ohne Pfarrer), dass die Gefangenen so viele Fächer öffnen, bis sie ihren Ausweis gefunden haben. Folgenden einfachen Fragestellungen könnten noch helfen:

Gehört jeder Gefangene zu einem Kreislauf?
Zu wieviel Kreisläufen kann ein Gefangener gehören?
Wieviel Gefangene machen Fächer des gleichen Kreislaufes auf?
Wieviel Fächer machen die Gefangenen, die zu einem Kreislauf, gehören auf?
Wann machen sie höchstens 25 Fächer auf?
Wann machen sie mehr als 25 Fächer auf?
Was ist die größte Anzahl schlechter Kreisläufe?
Kann der Pfarrer was tun, dass die, die ohne Pfarrer mehr als 25 Fächer aufmachen, nach dem Tausch weniger als 25 Fächer aufmachen?

Gruß Otmar

[Kolabord]

Ich glaube ich hab's:

Mehr ->

Alle Gefangenen, die sich in einem Kreislauf, der max. 25 Fächer umfasst befinden, finden ihren Ausweis. Der Pfarrer muss also dafür sorgen, dass keine Kreisluf größer ist. Das ist ihm immer möglich, da ja max. 1 Kreislauf mehr als 25 Fächer beeinhalten kann.

[Friedel]

Wenn aber alle ihre Fächer nach einem System öffnen, dann wären die Erfolge stark von einander Abhängig und zwar so stark, dass auch ohne den Pfarrer mit hohere Wahrscheinlichkeit ihr Fach finden...

Wie soll diese Abhängigkeit denn zustande kommen?. Schließlich erfahren de Gefangenen ja nichts von den Erfolgen der anderen Gefangenen. Imho ist die Wahrscheinlichkeit fast 0, dass alle ihre Ausweise finden. Der Prozentsatz der Wahrscheinlichkeit beginnt mit 0,0 und hat erst in der dreizehnten Nachkommastelle eine andere Zahl als eine 0. Durch den Pfarrer wird die Wahrscheinlichkeit vervierfacht, wodurch es wahrscheinlich eine Null weniger wird.

[Otmar]

Hallo Kolabord,
war'ne lange Story, aber jetzt ist es endlich raus!
Hoffe, es war nicht langweilig.

Da die Lösung in vielen Antworten verteilt ist, schreib ich sie nochmal zusammen und gebe auch meine Quelle, in der die Rechnungen zu den angegebenen Wahrscheinlichkeiten ohne Pfarrer angegeben sind, an. Man weiss heutzutage nie, was einem vorgeworfen wird, wenn man diesbezüglich nachlässig ist .

Mehr ->

Beratung der Gefangenen mit Pfarrer:
1) Nummerieren der Fächer von F1..F50
2) Nummerieren der Gefangenen von G1..G50
3) Strategie zum Öffnen der Fächer:
Vorerst gehen wir davon aus, dass jeder Gefangene so viele Fächer öffnet, bis er seinen Ausweis gefunden hat, also ggf. mehr als 25. Und zwar so: Ein Gefangener Gx öffnet zuerst Fx und findet dort den Ausweis von Gy. Er ist fertig wenn x=y. Sonst öffnet er Fy findet den Ausweis von Gz öffnet Fz und so weiter bis er seinen Ausweis gefunden hat. Mit dieser Strategie öffnet er Fach für Fach einer geschlossenen Fächer-Ausweis-Kette bis zum letzten Fach, in dem der Ausweis von Gx liegen muss, da das nächste Fach Fx ja das Folgefach vom letzten geöffneten Fach schon ganz zu Anfang geöffnet wurde. Jeder Gefangene, dessen Ausweis in dieser Fächer-Ausweis-Kette vorkommt, öffnet die gleichen Fächer, beginnend mit dem Fach, das Nachfolger des Faches mit seinem eigenen Ausweis ist. Er muss deshalb genau so viele Fächer öffnen, wie die Fächer-Ausweis-Kette Fächer hat.
Nun gehört jeder Gefangene zu genau einer Fächer-Ausweis-Kette und verschiedene Fächer-Ausweis-Ketten sind separat (da ja jedes Fach nur einen und nicht mehrere Nachfolger hat).
Wenn alle Fächer-Ausweis-Ketten höchstens 25 Fächer haben, kommen die Gefangenen frei, ohne dass der Pfarrer tauschen muss.
4) Aufgabe des Pfarrers:
Da die Fächer-Ausweis-Ketten separat sind, kann höchstens eine Fächer-Ausweis-Kette mehr als 25 Fächer haben. In dem Fall greift der Pfarrer ein und tauscht derart, dass die lange Fächer-Ausweis-Kette in zwei Ketten mit jeweils höchstens 25 Fächern zerlegt wird.
Das kann er z.B. so machen:
4.1. Der Pfarrer öffnet alle Fächer des Schrankes.
4.2. Er nimmt ein offenes Fach Fx und verfolgt die dort beginnende Fächer-Ausweis-Kette und zählt deren Fächer. Sind es weniger als 25, schließt er alle Fächer der Fächer-Ausweis-Kette und ist fertig, wenn danach höchstens 25 Fächer offen sind. Sind noch mehr offen, macht er bei 4.2. weiter. Hatte die Fächer-Ausweis-Kette mehr als 25 Fächer, tauscht er 2 Ausweise, die in 2 Fächern liegen, die in dieser Fächer-Ausweis-Kette 25 Fächer entfernt sind. Damit entsteht eine Fächer-Ausweis-Kette mit 25 Fächern. Also haben alle anderen Fächer-Ausweis-Ketten höchstens (50-25)=25 Fächer und der Pfarrer ist fertig, da es keine Fächer-Ausweis-Kette mit mehr als 25 Fächern gibt und jeder Gefangene seinen Ausweis finden wird.

Gefunden hatte ich die Problemstellung in der Mathematischen Unterhaltung in "Spektrum der Wissenschaft" im Juni Heft 2006. Der Artikel ist online kostenfrei verfügbar unter:
http://www.spektrum.de
DAS MAGAZIN
Suche Titel/Autor/Jahr
dort Titel: Freiheit für die Kombinatoriker
und Autor: Christoph Pöppe
eingeben und laden.

mir hat's gefallen. Also Prost auf die Lösung
Gruß Otmar

[Musagetes]

Hi Otmar,

das ist ein sehr interessantes Rätsel, nur hast du m. E. den Gefangen die Freiheit etwas zu früh geschenkt.

Zur Lösung hätte es noch etwas Zeit gebraucht.

Solche selbst erfüllenden Suchstrategien finde ich faszinierend.

Gruß
Musagetes

[Friedel]

Mit dieser Strategie öffnet er Fach für Fach einer geschlossenen Fächer-Ausweis-Kette bis zum letzten Fach, in dem der Ausweis von Gx liegen muss, ...

Hier ist der erste Fehler in dieser "Lösung". Warum sollte der Ausweis von Gx gerade in diesem Fach liegen? Er kann ach in einem beliebigen anderen Fach dieser Kette oder in einem Fach einer anderen Kette liegen.

Jeder Gefangene, dessen Ausweis in dieser Fächer-Ausweis-Kette vorkommt, ...

Dazu müsste jeder Gefangene wissen, welche Fächer zu einer Kette gehören und in welcher Kette sein Ausweis ist.

... beginnend mit dem Fach, das Nachfolger des Faches mit seinem eigenen Ausweis ist.

Und dazu müsste er sogar wissen, in welchem Fach sein Ausweis ist.

Ich lese wohl besser den Artikel.

[Kolabord]

Hier ist der erste Fehler in dieser "Lösung". Warum sollte der Ausweis von Gx gerade in diesem Fach liegen? Er kann ach in einem beliebigen anderen Fach dieser Kette oder in einem Fach einer anderen Kette liegen.

Dadurch, dass jedes Fach auf ein weiteres Verweisst, entstehen Ketten. Ist in Fx also der Ausweis von Gy, öfffnet Gx als nächstes Fy usw. Da das ganze ein Kreislauf ist, muss das letzte Fach einen Verweis auf Fx haben, also muss es denn Ausweis von Fx enthalten.

Dazu müsste jeder Gefangene wissen, welche Fächer zu einer Kette gehören und in welcher Kette sein Ausweis ist.

Das stimmt auch nicht, da sein Ausweis automatisch zu der Kette gehört, zu der Auch sein Fach gehört, da es sich ja um Kreisläufe handelt.

Und dazu müsste er sogar wissen, in welchem Fach sein Ausweis ist.

Tut er automatisch, wenn er sein eigenes Fach öffnet, da das Fach davor auf sein Fach verweisen, also auch seinen Ausweis enthalten muss.

[Otmar]

Hallo Friedel,

Mit dieser Strategie öffnet er Fach für Fach einer geschlossenen Fächer-Ausweis-Kette bis zum letzten Fach, in dem der Ausweis von Gx liegen muss, ...

Hier ist der erste Fehler in dieser "Lösung". Warum sollte der Ausweis von Gx gerade in diesem Fach liegen? Er kann ach in einem beliebigen anderen Fach dieser Kette oder in einem Fach einer anderen Kette liegen.

Die Frage ist berechtigt. Der Grund ist, das jeder Ausweis in genau einer Fächer-Ausweis-Kette liegt. Die Suchstrategie öffnet genau eine Fächer-Ausweis-Kette. In der Kette in der der Ausweis von Gx im Fach Fz liegt folgt das Fach Fx diesem Fach Fz. Deshalb ist Fx ein Fach der Fächer-Ausweis-Kette, die auch Fz mit dem Ausweis von Gx enthält. Und da Gx mit Fx beginnt öffnet Gx die Kette, die auch seinen Ausweis enthält.

Jeder Gefangene, dessen Ausweis in dieser Fächer-Ausweis-Kette vorkommt, ...

Dazu müsste jeder Gefangene wissen, welche Fächer zu einer Kette gehören und in welcher Kette sein Ausweis ist.

Auch berechtigt und wird mit der Antwort zur ersten Frage erledigt.

... beginnend mit dem Fach, das Nachfolger des Faches mit seinem eigenen Ausweis ist.

Und dazu müsste er sogar wissen, in welchem Fach sein Ausweis ist.

Nein, ich glaube hier liegt im Moment das Verständnisproblem. Denn Gx öffnet den Nachfolger des Faches Fz ohne z zu kennen. Gx öffnet Fx genau deshalb, weil dieses Fach seine Nummer und zwar x hat. Das das der Nachfolger seines Faches ist, weiss er, weil die geschlossenen Ausweis-Fächer-Ketten so aufgebaut sind und es ja irgendein Fach Fz geben muss, in dem sein Ausweis liegt.

Ich lese wohl besser den Artikel.

Ist auf jeden Fall zu empfehlen. Christoph Pöppe kann sehr auschaulich erklären, die angegebenen Beispiele erleichtern das Verständnis ungemein und der Artikel ist witzig geschrieben. Viel Spass dabei!
Gruß Otmar