Die Gefangenen von Zyklonien (Lösung)
Eigentlich stehen 3 Aufgaben zur Lösung an:
1. die eigentliche Aufgabe die Strategie zur Befreiung zu finden
2. die Unterstützung benennen, die der Anstaltspfarrer leisten kann
3. die Wahrscheinlichkeit, mit der die Gefangenen nach x Tagen frei sind.
2 3 4 5 6 1
Wie man sieht, ist die Verteilung der 100 Zettel (mit den Nummern 1-100) in die Schachteln (mit den Nummern 1-100) gerade eine solche Permutation der ersten 100 natürlichen Zahlen.
Na und, sieht noch recht langweilig aus.
Betrachtet man Permutationen genauer, erkennt man, dass es sehr wohl Unterschiede in der "Umordnung" (oder sollte ich besser sagen "Unordnung") der jeweils zweiten Zeile gibt.
Zunächst mal gibt es übereinander stehende Zahlenpaare ohne "Fehlstellung", z. B. steht unter der 5 im ersten Beispiel wieder die 5. Als zweiten Grad der Um(n)ordnung sollen sog. Transpositionen gelten, das sind Vertauschungen genauer zweier Zahlen untereinander, im 1. Beispiel die 1 mit der 2 oder auch die 1 mit der 5 im zweiten Beispiel. Und so wächst die Anzahl der Fehlstellungen immer weiter, z. B. ist
. . 3 4 . 6 (*)
. . 4 6 . 3
im ersten Beispiel noch eine Stufe "unordentlicher" als eine Transpostiton. Allgemein spricht man hier von sog. Zyklen der Länge r; so ist eine Transposition ein Zyklus der Länge 2, unser Zyklus (*) hat die Länge 3. Die Länge r eines Zyklus ist also gerade die Anzahl der Schritte, die man braucht um wieder beim Ausgangselement anzukommen: 3 auf 4, 4 auf 6, 6 auf 3 und so versteht sich auch der Name Zyklus. Formal betrachtet ist eine identische Zuordnung (5 auf 5), also ohne Fehlstellung, ein Zyklus der Länge 1.
Somit setzt sich die Permutation im ersten Beispiel aus 3 Zyklen der Längen 1, 2 und 3 zusammen.
Schauen wir, ob es verstanden ist: Beispiel 2 hat 3 Transpositionen (= 3 Zyklen der Länge 2), nämlich 1 auf 5, 5 auf 1 und 2 auf 4, 4 auf 2 und 3 auf 6, 6 auf 3. (Dabei ist es übrigens völlig unerheblich, wo man in einem Zyklus anfängt: 1 auf 5, 5 auf 1 ist natürlich das gleiche wie 5 auf 1, 1 auf 5).
Und das dritte Beispiel? Nun, das besteht aus genau einem Zyklus der Länge 6, nämlich 1 auf 2, 2 auf 3, 3 auf 4, 4 auf 5, 5 auf 6, 6 auf 1 und stellt damit das Höchstmaß an Um(n)ordnung dar, das bei einer Permutation von 6 natürlichen Zahlen möglich ist.
Wir halten fest: Ein Zyklus einer Permutation von n Zahlen hat maximal die Länge n.
Was hilft uns das alles denn nun bei unserem Gefangenenproblem?
Betrachten wir jetzt einmal unser Problem von Seiten der zur Verfügung stehenden Informationsmenge (Hinweis 5).
Die Verteilung der 100 Zettel auf die 100 Schachteln ist eine Permutation der ersten 100 natürlichen Zahlen, hatten wir gesagt.
Vor dem Öffnen der ersten Schachtel hat jeder Gefangene nur eine Information die er nützen kann, nämlich seine eigene Zellennummer. Was liegt näher, als die Schachtel mit dieser Nummer zu öffnen (wenn die Nummer nicht draufsteht, muss er eben zählen, Hinweis 3). Das Öffnen der Schachtel bringt eine weitere Information in Form einer weiteren Nummer: ist es seine eigene, ist er fertig (dies bedeutet, dass an dieser Stelle der Permutation keine Fehlstellung vorliegt) und braucht die restlichen Schachteln nicht mehr zu öffnen. Ist es aber nicht seine eigene, öffnet er nun die Schachtel mit dieser Nummer, d.h. er geht in der Permutation "auf" den nächsten Wert innerhalb des Zyklus in dem er sich gerade befindet. Und wieder gilt: wenn er seine Nummer findet (dann wäre es an dieser Stelle eine Transposition) ist er fertig, sonst: nächste Schachtel. Findet er nach r Schachtelöffnungen seine Nummer, hatte die zugrundeliegende Permutation dort einen Zyklus der Länge r.
Die in Hinweis 4 versprochenen Struktur ergibt sich aus dem mathematischen Satz: Jede Permutation läßt sich aus Zyklen zusammensetzen.
Um das noch besser zu verstehen, gehen wir einfach mal unsere obigen Beispiele durch. Der Einfachheit halber nehmen wir an, dass es sich nur um 6 Gefangene in 6 Zellen und 6 Schachteln handelt.
Unser Insasse sitzt in Zelle 4.
1. Beispiel
Er öffnet Schachtel 4 findet 6 (4 auf 6), öffnet 6 findet 3 (6 auf 3), öffnet 3 findet 4 (3 auf 4), hurra gefunden.
2. Beispiel
Er öffnet Schachtel 4 findet 2 (4 auf 2), öffnet 2 findet 4 (2 auf 4), hurra gefunden.
3. Beispiel
Er öffnet Schachtel 4 findet 5, öffnet 5 findet 6, öffnet 6 findet 1, öffn ... da pfeift der Schiedsrichter ab! Warum? Die Hälfte der Schachteln ist geöffnet (sind hier natürlich nur 6/2 = 3) und er hat seine Nummer nicht gefunden, der Tag ist vertan (es reicht ja, wenn schon einer seine Nummer nicht findet).
Und überhaupt, was wäre denn mit den anderen 5 Gefangenen in unserem Beispiel, würden sie mit dieser Strategie auch Erfolg haben und ihre Zellennummer finden, denn nur das führt ja zur Befreiung aller Insassen? Ja, man überzeuge sich selbst, dass in den Beispielen 1 und 2 auch alle anderen das gewünschte Ziel erreichen würden, damit also alle frei kämen, im dritten Beispiel fände keiner den Zettel mit seiner Zellennummer, da der Zyklus hier maximale Länge hat.
Was taugt also unsere Strategie?
Hinweis 2 hebt ja schon darauf ab, dass das Ganze auf eine Wahrscheinlichkeitsbetrachtung hinausläuft. Die Güte unserer Strategie wird also durch die Wahrscheinlichkeit bestimmt, mit der, einfach ausgerückt, der Fall des dritten Beispiels eintrifft. Dazu machen wir aber mal ein paar Vorüberlegungen.
Woran lag es denn überhaupt, dass Beispiel 3 so katastrophal schief ging und wieso klappte es in den Beispielen 1 und 2 mit allen Probanden?
Ich glaube, ohne große Beweise führen zu müssen, versteht man sofort, dass die Länge des längsten (und hier einzigen) Zyklus (im Beispiel 3 war sie 6) den Strich durch die Rechnung macht. Da das Schachtelöffnen bei 3 (allgemein bei n/2, n sei gerade Zahl) endet, wird ein Zyklus, der länger ist als n/2, die Probleme bereiten. (Die Nummer, mit der man in den Zyklus einsteigt, kommt immer als letzte aus den Schachteln.) Umgekehrt, wenn alle Zyklen kürzer oder gleichlang n/2 sind, werden die Zellennummern immer gefunden (Beispiele 1 und 2).
Noch etwas fällt uns auf / ein. Ein Zyklus, der länger als n/2, ist erscheint auf den ersten Blick als selten, warum? Es gibt höchstens einen pro Permutation, was sofort einleuchtet, denn die Länge der verschiedenen Zyklen addieren sich zur Permutationslänge n. Somit reduziert sich die Frage nach der Güte unserer Strategie darauf, wie wahrscheinlich bei einer zufällig gebildeten Permutation ein Zyklus der Länge größer n/2 ist.
Immerhin können wir jetzt die 2. Frage, die wir oben gestellt, haben definitiv beantworten:
Der Anstaltspfarrer erhält die Aufgabe, zu prüfen, ob es einen Zyklus länger als 50 gibt und wenn ja, ihn durch Vertauschen zweier Zettel so zu unterbrechen, dass es keinen solchen mehr gibt.
Das Misstrauen der Gefangenen richtete sich also gegen eine manipulierte Zettelverteilung, die immer einen Zyklus größer 50 erzeugt haben dürfte.
Bleibt also die Frage der Wahrscheinlichkeit nach dem Auftreten eines Zyklus länger als n/2, in unserer Aufgabe also größer 50.
Dazu habe ich zwei Lösungswege anzubieten, einen empirischen und einen exakten. Fangen wir mit dem empirischen Weg an.
Dazu habe ich ein kleines Computerprogramm in der Programmiersprache Pascal geschrieben, das unter Einsatz eines (Pseudo-) Zufallszahlengenerators x Permutationen der Länge 100 zufällig erzeugt, prüft, ob sie einen Zyklus länger 50 enthalten und somit die Anzahl der "günstigen" Fälle (also ohne Zyklus länger 50) zählt. Die gewünschte Wahrscheinlichkeit ergibt sich dann aus dem Quotienten der Anzahl der günstigen durch die der möglichen Fälle.
Das Programm lieferte bei x = 100.000.000 Versuchen eine Wahrscheinlichkeit von 0,31183036 für das Auftreten keines Zyklus der Länge größer 50.
Das Programm füge ich am Ende dieser Lösung als Download hinzu; es kann für eigene Experimente verwendet werden.
Die gemäß Wahrscheinlichkeitsrechnung exakte Lösung ist 1 - (1/51 + 1/52 + 1/53 + ... + 1/100) = 0,31182782069... in guter Übereinstimmung mit dem empirisch ermittelten Wert (Die Herleitung dieser Formel findet sich als PDF-Datei im Anhang).
Die Wahrscheinlichkeit, die Freiheit zu erlangen, ist also fast ein Drittel schon beim ersten Versuch. Man kann die täglichen Versuche des Schachtelöffnens als geometrische Verteilung (Variante 2) ansehen (das ist eine statistische Verteilung, die das Verhalten von Experimenten bis zum ersten Erfolg beschreibt) und so ausrechnen, dass nach 7 Tagen die Wahrscheinlichkeit, frei zu sein auf 0,9668.... angewachsen ist - gute Aussichten also für die Anstaltsinsassen.
Hier noch etwas mathematisches Bonusmaterial:
Zyklen.pdf
Zyklonien.pas
1. die eigentliche Aufgabe die Strategie zur Befreiung zu finden
2. die Unterstützung benennen, die der Anstaltspfarrer leisten kann
3. die Wahrscheinlichkeit, mit der die Gefangenen nach x Tagen frei sind.
Die Aufgabe findet sich auch an vielen Stellen im Internet, oft allerdings in einer Form, die das Finden der Lösung noch etwas schwerer macht, z. B. so:
...
Jeder Gefangene sitzt in einer eigenen Zelle. Jeden Tag einmal lässt der Direktor die Gefangenen nacheinander einzeln aus ihrer jeweiligen Zelle holen und in einen separaten Raum führen, in dem 100 geschlossene Schachteln stehen. In jeder Schachtel liegt ein Zettel mit dem Namen eines Gefangenen, es kommen alle Namen der Gefangenen genau einmal vor (es gibt keine doppelten Namen); die Verteilung der Zettel ist zufällig. Die beschrifteten Zettel in den Schachteln werden jeden Tag neu gemischt.
Jeder Gefangene muss nun nach eigener Wahl die Hälfte, also 50 der 100 Schachteln öffnen und schauen, ob sein Name in einer der 50 Schachteln vorkommt. Dann werden die Schachteln wieder verschlossen und der nächste Gefangene muss nun seinerseits das gleiche tun. Wenn jeder der 100 Häftlinge seinen eigenen Namen in einer der von ihm geöffneten 50 Schachteln findet, dann werden alle 100 Häftlinge freigelassen, sonst nicht.
...
Quasi als ersten Hinweis habe ich die Aufgabe schon in Richtung der Lösungsidee gestellt, indem ich von vorne herein die Nummerierung von Zellen und Zetteln eingebracht habe.
In der Mathematik gibt es den Begriff der "Permutation" (Vertauschung); dabei handelt es sich um die Umordnng von n natürlichen Zahlen, wie folgende Beispiele mit 6 Zahlen zeigen:
1 2 3 4 5 6 geordnete 6 Zahlen
2 1 4 6 5 3 Umgeordnete 6 Zahlen
oder
1 2 3 4 5 6
5 4 6 2 1 3
oder
1 2 3 4 5 62 3 4 5 6 1
Wie man sieht, ist die Verteilung der 100 Zettel (mit den Nummern 1-100) in die Schachteln (mit den Nummern 1-100) gerade eine solche Permutation der ersten 100 natürlichen Zahlen.
Na und, sieht noch recht langweilig aus.
Betrachtet man Permutationen genauer, erkennt man, dass es sehr wohl Unterschiede in der "Umordnung" (oder sollte ich besser sagen "Unordnung") der jeweils zweiten Zeile gibt.
Zunächst mal gibt es übereinander stehende Zahlenpaare ohne "Fehlstellung", z. B. steht unter der 5 im ersten Beispiel wieder die 5. Als zweiten Grad der Um(n)ordnung sollen sog. Transpositionen gelten, das sind Vertauschungen genauer zweier Zahlen untereinander, im 1. Beispiel die 1 mit der 2 oder auch die 1 mit der 5 im zweiten Beispiel. Und so wächst die Anzahl der Fehlstellungen immer weiter, z. B. ist
. . 3 4 . 6 (*)
. . 4 6 . 3
im ersten Beispiel noch eine Stufe "unordentlicher" als eine Transpostiton. Allgemein spricht man hier von sog. Zyklen der Länge r; so ist eine Transposition ein Zyklus der Länge 2, unser Zyklus (*) hat die Länge 3. Die Länge r eines Zyklus ist also gerade die Anzahl der Schritte, die man braucht um wieder beim Ausgangselement anzukommen: 3 auf 4, 4 auf 6, 6 auf 3 und so versteht sich auch der Name Zyklus. Formal betrachtet ist eine identische Zuordnung (5 auf 5), also ohne Fehlstellung, ein Zyklus der Länge 1.
Somit setzt sich die Permutation im ersten Beispiel aus 3 Zyklen der Längen 1, 2 und 3 zusammen.
Schauen wir, ob es verstanden ist: Beispiel 2 hat 3 Transpositionen (= 3 Zyklen der Länge 2), nämlich 1 auf 5, 5 auf 1 und 2 auf 4, 4 auf 2 und 3 auf 6, 6 auf 3. (Dabei ist es übrigens völlig unerheblich, wo man in einem Zyklus anfängt: 1 auf 5, 5 auf 1 ist natürlich das gleiche wie 5 auf 1, 1 auf 5).
Und das dritte Beispiel? Nun, das besteht aus genau einem Zyklus der Länge 6, nämlich 1 auf 2, 2 auf 3, 3 auf 4, 4 auf 5, 5 auf 6, 6 auf 1 und stellt damit das Höchstmaß an Um(n)ordnung dar, das bei einer Permutation von 6 natürlichen Zahlen möglich ist.
Wir halten fest: Ein Zyklus einer Permutation von n Zahlen hat maximal die Länge n.
Was hilft uns das alles denn nun bei unserem Gefangenenproblem?
Betrachten wir jetzt einmal unser Problem von Seiten der zur Verfügung stehenden Informationsmenge (Hinweis 5).
Die Verteilung der 100 Zettel auf die 100 Schachteln ist eine Permutation der ersten 100 natürlichen Zahlen, hatten wir gesagt.
Vor dem Öffnen der ersten Schachtel hat jeder Gefangene nur eine Information die er nützen kann, nämlich seine eigene Zellennummer. Was liegt näher, als die Schachtel mit dieser Nummer zu öffnen (wenn die Nummer nicht draufsteht, muss er eben zählen, Hinweis 3). Das Öffnen der Schachtel bringt eine weitere Information in Form einer weiteren Nummer: ist es seine eigene, ist er fertig (dies bedeutet, dass an dieser Stelle der Permutation keine Fehlstellung vorliegt) und braucht die restlichen Schachteln nicht mehr zu öffnen. Ist es aber nicht seine eigene, öffnet er nun die Schachtel mit dieser Nummer, d.h. er geht in der Permutation "auf" den nächsten Wert innerhalb des Zyklus in dem er sich gerade befindet. Und wieder gilt: wenn er seine Nummer findet (dann wäre es an dieser Stelle eine Transposition) ist er fertig, sonst: nächste Schachtel. Findet er nach r Schachtelöffnungen seine Nummer, hatte die zugrundeliegende Permutation dort einen Zyklus der Länge r.
Die in Hinweis 4 versprochenen Struktur ergibt sich aus dem mathematischen Satz: Jede Permutation läßt sich aus Zyklen zusammensetzen.
Um das noch besser zu verstehen, gehen wir einfach mal unsere obigen Beispiele durch. Der Einfachheit halber nehmen wir an, dass es sich nur um 6 Gefangene in 6 Zellen und 6 Schachteln handelt.
Unser Insasse sitzt in Zelle 4.
1. Beispiel
Er öffnet Schachtel 4 findet 6 (4 auf 6), öffnet 6 findet 3 (6 auf 3), öffnet 3 findet 4 (3 auf 4), hurra gefunden.
2. Beispiel
Er öffnet Schachtel 4 findet 2 (4 auf 2), öffnet 2 findet 4 (2 auf 4), hurra gefunden.
3. Beispiel
Er öffnet Schachtel 4 findet 5, öffnet 5 findet 6, öffnet 6 findet 1, öffn ... da pfeift der Schiedsrichter ab! Warum? Die Hälfte der Schachteln ist geöffnet (sind hier natürlich nur 6/2 = 3) und er hat seine Nummer nicht gefunden, der Tag ist vertan (es reicht ja, wenn schon einer seine Nummer nicht findet).
Und überhaupt, was wäre denn mit den anderen 5 Gefangenen in unserem Beispiel, würden sie mit dieser Strategie auch Erfolg haben und ihre Zellennummer finden, denn nur das führt ja zur Befreiung aller Insassen? Ja, man überzeuge sich selbst, dass in den Beispielen 1 und 2 auch alle anderen das gewünschte Ziel erreichen würden, damit also alle frei kämen, im dritten Beispiel fände keiner den Zettel mit seiner Zellennummer, da der Zyklus hier maximale Länge hat.
Was taugt also unsere Strategie?
Hinweis 2 hebt ja schon darauf ab, dass das Ganze auf eine Wahrscheinlichkeitsbetrachtung hinausläuft. Die Güte unserer Strategie wird also durch die Wahrscheinlichkeit bestimmt, mit der, einfach ausgerückt, der Fall des dritten Beispiels eintrifft. Dazu machen wir aber mal ein paar Vorüberlegungen.
Woran lag es denn überhaupt, dass Beispiel 3 so katastrophal schief ging und wieso klappte es in den Beispielen 1 und 2 mit allen Probanden?
Ich glaube, ohne große Beweise führen zu müssen, versteht man sofort, dass die Länge des längsten (und hier einzigen) Zyklus (im Beispiel 3 war sie 6) den Strich durch die Rechnung macht. Da das Schachtelöffnen bei 3 (allgemein bei n/2, n sei gerade Zahl) endet, wird ein Zyklus, der länger ist als n/2, die Probleme bereiten. (Die Nummer, mit der man in den Zyklus einsteigt, kommt immer als letzte aus den Schachteln.) Umgekehrt, wenn alle Zyklen kürzer oder gleichlang n/2 sind, werden die Zellennummern immer gefunden (Beispiele 1 und 2).
Noch etwas fällt uns auf / ein. Ein Zyklus, der länger als n/2, ist erscheint auf den ersten Blick als selten, warum? Es gibt höchstens einen pro Permutation, was sofort einleuchtet, denn die Länge der verschiedenen Zyklen addieren sich zur Permutationslänge n. Somit reduziert sich die Frage nach der Güte unserer Strategie darauf, wie wahrscheinlich bei einer zufällig gebildeten Permutation ein Zyklus der Länge größer n/2 ist.
Immerhin können wir jetzt die 2. Frage, die wir oben gestellt, haben definitiv beantworten:
Der Anstaltspfarrer erhält die Aufgabe, zu prüfen, ob es einen Zyklus länger als 50 gibt und wenn ja, ihn durch Vertauschen zweier Zettel so zu unterbrechen, dass es keinen solchen mehr gibt.
Das Misstrauen der Gefangenen richtete sich also gegen eine manipulierte Zettelverteilung, die immer einen Zyklus größer 50 erzeugt haben dürfte.
Bleibt also die Frage der Wahrscheinlichkeit nach dem Auftreten eines Zyklus länger als n/2, in unserer Aufgabe also größer 50.
Dazu habe ich zwei Lösungswege anzubieten, einen empirischen und einen exakten. Fangen wir mit dem empirischen Weg an.
Dazu habe ich ein kleines Computerprogramm in der Programmiersprache Pascal geschrieben, das unter Einsatz eines (Pseudo-) Zufallszahlengenerators x Permutationen der Länge 100 zufällig erzeugt, prüft, ob sie einen Zyklus länger 50 enthalten und somit die Anzahl der "günstigen" Fälle (also ohne Zyklus länger 50) zählt. Die gewünschte Wahrscheinlichkeit ergibt sich dann aus dem Quotienten der Anzahl der günstigen durch die der möglichen Fälle.
Das Programm lieferte bei x = 100.000.000 Versuchen eine Wahrscheinlichkeit von 0,31183036 für das Auftreten keines Zyklus der Länge größer 50.
Das Programm füge ich am Ende dieser Lösung als Download hinzu; es kann für eigene Experimente verwendet werden.
Die gemäß Wahrscheinlichkeitsrechnung exakte Lösung ist 1 - (1/51 + 1/52 + 1/53 + ... + 1/100) = 0,31182782069... in guter Übereinstimmung mit dem empirisch ermittelten Wert (Die Herleitung dieser Formel findet sich als PDF-Datei im Anhang).
Die Wahrscheinlichkeit, die Freiheit zu erlangen, ist also fast ein Drittel schon beim ersten Versuch. Man kann die täglichen Versuche des Schachtelöffnens als geometrische Verteilung (Variante 2) ansehen (das ist eine statistische Verteilung, die das Verhalten von Experimenten bis zum ersten Erfolg beschreibt) und so ausrechnen, dass nach 7 Tagen die Wahrscheinlichkeit, frei zu sein auf 0,9668.... angewachsen ist - gute Aussichten also für die Anstaltsinsassen.
Hier noch etwas mathematisches Bonusmaterial:
Zyklen.pdf
Zyklonien.pas