Gefangene und Hüte



  • 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.



  • Die Strategie könnte aber ansonsten darauf beruhen, dass die anderen Antworten in die eigene Antwort einfliessen.



  • SG1 schrieb:

    Die Strategie könnte aber ansonsten darauf beruhen, dass die anderen Antworten in die eigene Antwort einfliessen.

    Gefangener G_n kann doch die Antworten aller Gefangenen G_j mit j>n ermitteln, weil er sieht ja alles, was diese sehen, und die Strategie hat man ja vorher vereinbart.


  • Mod

    Gregor schrieb:

    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.

    Erstmal ein ganz bisschen formalisieren, um sauberer argumentieren zu können.
    Definition: Eine Hutverteilung ist eine Funktion $$f\colon \mathbb{N} \to {\mathrm{rot}, \mathrm{blau}}$$.
    Definition: Zwei Hutverteilungen f, g sind äquivalent genau dann, wenn f und g sich nur an endlich vielen Punkten unterscheiden. In Symbolen: f ~ g gilt genau dann, wenn f(n) = g(n) für alle bis auf endlich viele n.

    Dann könnte man folgendes machen.
    Angenommen, die "echte" Hutverteilung ist f. Die Gefangenen kennen f nicht, aber sie sehen immer ein Segment von f, nämlich alle f(n) für n > Nummer des aktuellen Gefangenen.

    Jetzt ist es so, dass das "äquivalent" nach obiger Definition eine Äquivalenzrelation auf den Hutverteilungen ist. Das bedeutet, dass die Menge aller Hutverteilungen in Äquivalenzklassen zerfällt.
    Der Trick ist nun, wenn man f nur an endlich vielen Stellen nicht kennt, kann man trotzdem sagen, in welcher Äquivalenzklasse f ist; das funktioniert aus dem Grund, weil "äquivalent" gerade so definiert wurde, dass endlich viele "Fehler" oder "unbekannte Stellen" nicht stören. Jeder Gefangene kann also die genaue Äquivalenzklasse nennen, in der die richtige Hutverteilung liegt. Jeder Gefangene hat dann also dieselbe Äquivalenzklasse im Sinn.

    Eine Äquivalenzklasse ist eine Menge von Hutverteilungen. Wenn jetzt alle Gefangenen dasselbe Element aus dieser Äquivalenzklasse nennen, nennen sie irgendeine Funktion g. Alle Gefangenen nennen dasselbe g, weil sie dieselbe Äquivalenzklasse im Sinn haben. Weil g und f (die richtige Hutverteilung) in derselben Äquivalenzklasse liegen, unterscheiden sich g und f höchstens an endlich vielen Stellen. Also raten höchstens endlich viele Gefangene falsch.

    Die Strategie ist also:

    1. Vereinbare für jede Äquivalenzklasse, welche Hutverteilung daraus genannt wird.
    2. Für den n-ten Gefangenen: Schaue nach, in welcher Äquivalenzklasse die richtige (unbekannte) Hutverteilung liegt und nimm das in Schritt 1) vereinbarte Element g dieser Äquivalenzklasse. Sage "Die Farbe meines Hutes ist g(n)".

    (Um es nochmal zu betonen: Alle Gefangenen werden in Schritt 2 dasselbe g finden, weil alle dieselbe Äquivalenzklasse finden.)



  • Hier mal eine Lösung:

    der letzte(der alle Hüte sieht) beginnt(Er sei Nummer 1).

    1. Er sagt die Hutfarbe des Vorgängers (->man muss annehmen, dass er dadurch falsch liegt bei seinem eigenen Hut)
    2. Nummer 2 weiß nun seine Hutfarbe. Sollte Nummer 3 die gleiche Farbe haben, sagt er seine Hutfarbe und liegt damit richtig. Nummer 3 weiß nun auch, dass er die gleiche Farbe hat. Sollte NUmmer 3 aber genau die andere Farbe haben, sagt Nummer 2 nichts. Wenn N2 z.b. 3 Sekunden lang nichts gesagt hat, weiß N3, dass er genau die andere Hutfarbe hat, wie N1 gesagt hat.
    3. Nun macht N3 genau das gleiche, also er sagt seinen Hut, wenn er die gleiche Farbe hat wie sein Vorgänger ansonsten nicht.
    so geht das immer weiter, bis zum vordersten, der dann einfach seine Hutfarbe sagen kann.
    4. Nun können noch alle, die zwischendurch nichts gesagt haben ihre Farbe nennen

    => Maximal der erste rät falsch

    Bsp.:

    Farbe  R  B  R  R  R  B  B  R  B
    sagt   B  -  R  R  -  B  -  -  B
    sagt      B        R     B  R
    r/f    f  r  r  r  r  r  r  r  r
    


  • DerBaer schrieb:

    so geht das immer weiter, bis zum vordersten, der dann einfach seine Hutfarbe sagen kann.
    4. Nun können noch alle, die zwischendurch nichts gesagt haben ihre Farbe nennen

    Es gibt keinen Vordersten.
    Schritt 4 wird so nie ausgeführt.



  • volkard schrieb:

    DerBaer schrieb:

    so geht das immer weiter, bis zum vordersten, der dann einfach seine Hutfarbe sagen kann.
    4. Nun können noch alle, die zwischendurch nichts gesagt haben ihre Farbe nennen

    Es gibt keinen Vordersten.
    Schritt 4 wird so nie ausgeführt.

    Dann wartet er halt 3 Sekunden und sagt erst danach seine Farbe. Es dauert sowieso unendlich lange, bis alle was gesagt haben xD


Anmelden zum Antworten