Gefangene und Hüte



  • Hi.

    Mir wurde letzt ein mathematisches Rätsel gestellt:

    Man hat abzählbar unendlich viele Gefangene, die in einer Reihe aufgestellt sind. Es gibt einen ersten Gefangenen und jeder Gefangene sieht genau die Gefangenen mit größerer Nummer. Zum Beispiel alle, die rechts von ihm stehen. Jetzt wird den Gefangenen gesagt, dass man Ihnen Hüte aufsetzen wird. Die Hüte haben jeweils eine von zwei Farben: Rot und Blau. Kein Gefangener sieht seinen eigenen Hut und den Gefangenen wird gesagt, dass sie jeweils die Farbe ihres Hutes raten müssen. Wenn nur endlich viele Gefangene beim Raten falsch liegen, dann werden alle Gefangene freigelassen. So: Bevor den Gefangenen die Hüte aufgesetzt werden, dürfen sie eine Strategie absprechen, nach der sie beim Raten vorgehen werden. Danach gibt es keine Kommunikation mehr zwischen den Gefangenen und jeder Gefangene sieht nur noch die Gefangenen rechts von ihm und natürlich die Hüte, die diese Gefangenen aufhaben. Die Frage ist: Gibt es eine Strategie, nach der die Gefangenen raten können, die dazu führt, dass alle frei kommen?

    Dieses Rätsel wurde mir von einem Mathestudenten gestellt, der sehr genau begründet hat, dass es - entgegen der Intuition - so eine Strategie gibt. Er hat sie mir erklärt und ich habe natürlich nichts verstanden. Deshalb die Frage an Euch: Wie könnte das funktionieren?!



  • Gregor schrieb:

    Wie könnte das funktionieren?!

    Es kann keine Strategie geben, bei der es _immer_ funktioniert.
    Angenommen, die Hüte sind unabhängig zufällig gleichverteilt, also jeder Gefangene hat mit 50% Wahrscheinlichkeit einen roten Hut und mit 50% einen blauen. Dann kann er von den anderen Hüten nicht auf den eigenen Hut schließen. Also gibt es unendlich viele Gefangene, die falsch raten, egal welche Strategie sie verfolgen. Dies gilt "fast sicher", das heißt für nicht entartete Verteilungen. Davon gibt es genügend, also kann es keine sichere Strategie geben.


  • Mod

    empgodot schrieb:

    Angenommen, die Hüte sind unabhängig zufällig gleichverteilt, also jeder Gefangene hat mit 50% Wahrscheinlichkeit einen roten Hut und mit 50% einen blauen. Dann kann er von den anderen Hüten nicht auf den eigenen Hut schließen. Also gibt es unendlich viele Gefangene, die falsch raten, egal welche Strategie sie verfolgen.

    Das letzte "also" versteh ich nicht. Nur weil ein Gefangener nicht weiß, ob er richtig rät, heißt ja nicht, dass er falsch rät.



  • empgodot schrieb:

    Gregor schrieb:

    Wie könnte das funktionieren?!

    Es kann keine Strategie geben, bei der es _immer_ funktioniert.
    Angenommen, die Hüte sind unabhängig zufällig gleichverteilt, also jeder Gefangene hat mit 50% Wahrscheinlichkeit einen roten Hut und mit 50% einen blauen. Dann kann er von den anderen Hüten nicht auf den eigenen Hut schließen. Also gibt es unendlich viele Gefangene, die falsch raten, egal welche Strategie sie verfolgen. Dies gilt "fast sicher", das heißt für nicht entartete Verteilungen. Davon gibt es genügend, also kann es keine sichere Strategie geben.

    Den Beweis halte ich nicht für schlüssig.
    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.
    Danach kann G2 mit sicherheit seine eigene Farbe richtig raten.
    Allerdings verzichtet er dabei darauf, Wissen weiterzugeben.

    Sagen wir mal jeder Gefangene mit einer ungeraden Zahl rät die Farbe seine Nachfolgers. Und jeder mit einer geraden Zahl rät dann richtig.
    Dann raten nur noch höchstens die Hälfte der Gefangenen falsch. Leider sind das noch unendlich viele.
    Kann man eine Codierung basteln, daß nur noch endlich viele falsch raten?



  • Gregor schrieb:

    Danach gibt es keine Kommunikation mehr zwischen den Gefangenen

    volkard schrieb:

    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.

    Ich verstehe die Aufgabe so, dass die Gefangenen die Tipps der anderen Gefangenen nicht hören. Oder meinst du das anders?



  • empgodot schrieb:

    Gregor schrieb:

    Danach gibt es keine Kommunikation mehr zwischen den Gefangenen

    volkard schrieb:

    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.

    Ich verstehe die Aufgabe so, dass die Gefangenen die Tipps der anderen Gefangenen nicht hören. Oder meinst du das anders?

    Hast Du richtig verstanden. Allerdings vermute ich, dass das gar keinen Unterschied macht.



  • empgodot schrieb:

    Gregor schrieb:

    Danach gibt es keine Kommunikation mehr zwischen den Gefangenen

    volkard schrieb:

    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.

    Ich verstehe die Aufgabe so, dass die Gefangenen die Tipps der anderen Gefangenen nicht hören. Oder meinst du das anders?

    Gregor schrieb:

    dürfen sie eine Strategie absprechen, nach der sie beim Raten vorgehen werden

    hatte ich so interpretiert, daß das Raten selbst öffentlich ist. Anderenfalls wäre die Aufgabe wohl Quatsch und Deinen Beweis würde ich anerkennen.


  • Mod

    volkard schrieb:

    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.
    Danach kann G2 mit sicherheit seine eigene Farbe richtig raten.
    Allerdings verzichtet er dabei darauf, Wissen weiterzugeben.

    Sagen wir mal jeder Gefangene mit einer ungeraden Zahl rät die Farbe seine Nachfolgers. Und jeder mit einer geraden Zahl rät dann richtig.
    Dann raten nur noch höchstens die Hälfte der Gefangenen falsch. Leider sind das noch unendlich viele.
    Kann man eine Codierung basteln, daß nur noch endlich viele falsch raten?

    Wenn nur endlich viele Gefangene falsch raten dürfen, dann muss es eine Zahl X geben, sodass alle Gefangenen mit größeren Nummern als X richtig raten. Gefangener X ist also der letzte, der falsch raten darf.
    Die Gefangenen 1 bis X können jeweils "rot" oder "blau" sagen. Sie können also X Bits an Informationen weitergeben, mehr nicht. Mit X Bits kann man 2^X verschiedene Hut-Verteilungen beschreiben. Das wird nicht ausreichen, damit alle Gefangenen nach dem X-ten Gefangenen richtig raten können, weil es unendlich viele verschiedene Hutverteilungen gibt.

    (Dieses Posting gilt unter der [laut empgodot vermutlich falschen] Annahme, dass die Gefangenen der Reihe nach raten und sich gegenseitig hören.)



  • volkard schrieb:

    hatte ich so interpretiert, daß das Raten selbst öffentlich ist. Anderenfalls wäre die Aufgabe wohl Quatsch und Deinen Beweis würde ich anerkennen.

    Der Punkt ist, glaube ich, dass es unendlich viele Gefangene sind. Und wenn Unendlichkeiten ins Spiel kommen, dann kann man plötzlich Sachen konstruieren, mit denen man so erstmal nicht rechnet. Wie gesagt: Die Tatsache, dass es da eine Lösung geben soll, ist völlig unintuitiv.



  • Christoph schrieb:

    volkard schrieb:

    G1 kann absichtlich falsch raten. Zum Beispiel rät er einfach die Farbe von G2.
    So läßt sich Wissen weiterleiten.
    Danach kann G2 mit sicherheit seine eigene Farbe richtig raten.
    Allerdings verzichtet er dabei darauf, Wissen weiterzugeben.

    Sagen wir mal jeder Gefangene mit einer ungeraden Zahl rät die Farbe seine Nachfolgers. Und jeder mit einer geraden Zahl rät dann richtig.
    Dann raten nur noch höchstens die Hälfte der Gefangenen falsch. Leider sind das noch unendlich viele.
    Kann man eine Codierung basteln, daß nur noch endlich viele falsch raten?

    Wenn nur endlich viele Gefangene falsch raten dürfen, dann muss es eine Zahl X geben, sodass alle Gefangenen mit größeren Nummern als X richtig raten. Gefangener X ist also der letzte, der falsch raten darf.
    Die Gefangenen 1 bis X können jeweils "rot" oder "blau" sagen. Sie können also X Bits an Informationen weitergeben, mehr nicht. Mit X Bits kann man 2^X verschiedene Hut-Verteilungen beschreiben. Das wird nicht ausreichen, damit alle Gefangenen nach dem X-ten Gefangenen richtig raten können, weil es unendlich viele verschiedene Hutverteilungen gibt.

    (Dieses Posting gilt unter der [laut empgodot vermutlich falschen] Annahme, dass die Gefangenen der Reihe nach raten und sich gegenseitig hören.)

    Also muß die Reihenfolge auch noch geändert werden.
    Ich denke da an sowas, wie daß der erste die Parität (Anzahl der Blauen modulo2) der Hüte 2-1000 herausposaunt. Und dann können die Gefangegen 2-1000 korrekt raten. Also n/1000 kriege ich schon. Vermutlich auch log2(n). Aber das ist noch nicht stark genug. Und ich kann einfach nicht in Endlich vielen Schritten nach ganz hinten hinspringen, weil es keinen letzten Gefangegen gibt.

    (Dieses Posting gilt unter der [laut empgodot vermutlich falschen] Annahme, dass die Gefangenen nach einem vorher abgesprochenen Verfahren raten und sich gegenseitig hören.)


  • Mod

    Ich möchte nochmal auf den Unterschied zwischen "Gefangener n rät richtig" und "Gefangener n weiß seine Hutfarbe" zurückkommen.

    Wenn ein Gefangener nur rote Hüte sieht, dann wäre doch eine vernünftige Strategie, "rot" zu raten. Auch wenn dann kein Gefangener weiß, ob er richtig rät, es werden höchstens endlich viele falsch liegen, oder nicht?



  • Christoph schrieb:

    Wenn ein Gefangener nur rote Hüte sieht, dann wäre doch eine vernünftige Strategie, "rot" zu raten.

    Das kann ich nicht erkennen.

    Christoph schrieb:

    Auch wenn dann kein Gefangener weiß, ob er richtig rät, es werden höchstens endlich viele falsch liegen, oder nicht?

    Das sehe ich auch nicht.

    Klar, es können zufällig nur endlich viele falsch liegen, obwohl kein einziger weiß, ob er richtig geraten hatte.



  • Wenn man irgendwie weiche Tips nach vorne geben könnte, bzw Tips über wachsende Hutmengen, so daß die Wahrscheinlichkeit des Richtig-Ratens je weiter vorne, desto wahrscheinlicher wird. Dann könnte eine Unendliche Reihe mit endlichem Wert vielleicht...


  • Mod

    volkard schrieb:

    Christoph schrieb:

    Wenn ein Gefangener nur rote Hüte sieht, dann wäre doch eine vernünftige Strategie, "rot" zu raten.

    Das kann ich nicht erkennen.

    Christoph schrieb:

    Auch wenn dann kein Gefangener weiß, ob er richtig rät, es werden höchstens endlich viele falsch liegen, oder nicht?

    Das sehe ich auch nicht.

    Klar, es können zufällig nur endlich viele falsch liegen, obwohl kein einziger weiß, ob er richtig geraten hatte.

    Angenommen, Gefangener X sieht nur rote Hüte und rät "mein Hut ist rot".
    Ob er richtig oder falsch liegt, weiß er nicht.

    Jetzt kommt Gefangener X+1. Er sieht auch lauter rote Hüte. Da er dieselbe Strategie wie Gefangener X hat, wird auch er raten "mein Hut ist rot".
    Ob er richtig oder falsch liegt, weiß er nicht.

    Gefangener X hat aber gesehen, dass X+1 einen roten Hut hat. Also muss X+1 richtig liegen. X+2 muss dann auch richtig liegen und alle restlichen Gefangenen ebenfalls.



  • Verstehe ich nicht. Daraus kann ich nur lesen "Falls es nur rote Hüte sind, gibt es eine gute Strategie".



  • volkard schrieb:

    Verstehe ich nicht. Daraus kann ich nur lesen "Falls es nur rote Hüte sind, gibt es eine gute Strategie".

    Ja, das ist ja schon ein Schritt in die richtige Richtung.


  • Mod

    volkard schrieb:

    Verstehe ich nicht. Daraus kann ich nur lesen "Falls es nur rote Hüte sind, gibt es eine gute Strategie".

    Die Aussage, die ich bewiesen habe, ist ein bisschen stärker (aber nicht viel): Falls irgendein Gefangener nur rote Hüte sieht, gibt es eine gute Strategie.
    Solange es also einen Punkt gibt, ab dem nur noch rote Hüte kommen, gibt es eine gute Strategie.



  • Christoph schrieb:

    volkard schrieb:

    Verstehe ich nicht. Daraus kann ich nur lesen "Falls es nur rote Hüte sind, gibt es eine gute Strategie".

    Die Aussage, die ich bewiesen habe, ist ein bisschen stärker (aber nicht viel): Falls irgendein Gefangener nur rote Hüte sieht, gibt es eine gute Strategie.
    Solange es also einen Punkt gibt, ab dem nur noch rote Hüte kommen, gibt es eine gute Strategie.

    Ok, jeder Gefangene kann also versuchen, ein Muster in der Hutfolge rechts von ihm zu erkennen und dieses Muster dann auf seinen Hut zu extrapolieren. Aber ich glaube nicht, dass es da immer ein Muster geben muss.



  • Ich hab mal google angeworfen und es scheint wirklich so zu sein, dass die Gefangenen die Antworten der anderen NICHT hören.



  • SG1 schrieb:

    Ich hab mal google angeworfen und es scheint wirklich so zu sein, dass die Gefangenen die Antworten der anderen NICHT hören.

    Das ist egal, weil sie können sich vorher auf eine Strategie einigen.


Anmelden zum Antworten