Gefangene und Hüte

[SG1]

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

[Mr. N]

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.

[Christoph]

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

[DerBaer]

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

[volkard]

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.

[DerBaer]

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

[SG1]

DerBaer schrieb:

Es dauert sowieso unendlich lange, bis alle was gesagt haben xD

Nein, es können alle gleichzeitig etwas sagen. Wie das geht, hat Christoph ja schon gesagt.

[Christoph]

DerBaer schrieb:

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.

Durch "3 Sekunden warten" wird Information übertragen. Jegliche Kommunikation ist laut Aufgabenstellung aber verboten.

[dkdlkasldkjf asd]

@Christoph: Ich sehe noch nicht dass die Äquivalenzklassen existieren. Kannst du sie explizit angeben?

[Jester]

dkdlkasldkjf asd schrieb:

@Christoph: Ich sehe noch nicht dass die Äquivalenzklassen existieren. Kannst du sie explizit angeben?

i) Reflexivität: Jede Hutverteilung ist mit sich selbst äquivalent, sie unterscheidet sich nämlich an 0 Stellen.

ii) Symmetrie: wenn ich f nur an endlich vielen Stellen ändern muß um g zu erhalten gilt das umgekehrt ebenso

iii) Transitivität: wenn ich durch ändern endlich vieler stellen von f nach g umbauen kann und ebenso mit endlich vielen änderungen von g nach h komme, dann brauche ich auch nur endliche viele schritte um von f nach h zu kommen.

Also ist das eine Äquivalenzrelation ... und die induziert auf kanonische Art und Weise Äquivalenzklassen:

[f] := { g | f unterscheidet sich von g nur an endlich vielen Stellen }

[dkdlkasldkjf asd]

Jester schrieb:

dkdlkasldkjf asd schrieb:

@Christoph: Ich sehe noch nicht dass die Äquivalenzklassen existieren. Kannst du sie explizit angeben?

i) Reflexivität: Jede Hutverteilung ist mit sich selbst äquivalent, sie unterscheidet sich nämlich an 0 Stellen.

ii) Symmetrie: wenn ich f nur an endlich vielen Stellen ändern muß um g zu erhalten gilt das umgekehrt ebenso

iii) Transitivität: wenn ich durch ändern endlich vieler stellen von f nach g umbauen kann und ebenso mit endlich vielen änderungen von g nach h komme, dann brauche ich auch nur endliche viele schritte um von f nach h zu kommen.

Also ist das eine Äquivalenzrelation ... und die induziert auf kanonische Art und Weise Äquivalenzklassen:

[f] := { g | f unterscheidet sich von g nur an endlich vielen Stellen }

Ah ich verstehe, und habe wieder mal falsch gefragt. Was ich meinte war: Kann man die Repräsentanten der Äquivalenzklassen angeben / so beschreiben dass jeder Gefangene den Repräsentanten auch findet?

[Jester]

dkdlkasldkjf asd schrieb:

Was ich meinte war: Kann man die Repräsentanten der Äquivalenzklassen angeben / so beschreiben dass jeder Gefangene den Repräsentanten auch findet?

Hm, das hängt wohl stark davon ab was Du annimmst was die gefangenen so alles können. Allein die Annahme, dass sie es in endlicher Zeit schaffen sich die Hutverteilung anzuschauen ist etwas unrealistisch.

Aus dem gleichen Grund kann es auch kein Verfahren geben, das in endlich vielen Schritten den Repräsentanten bestimmt. Einen richtigen Algorithmus kann es also nicht geben.

[Christoph]

Christoph schrieb:

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)".

Genau genommen braucht man für Schritt 1) in meinem Posting sogar das Auswahlaxiom.

[Bashar]

http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle#Countably_Infinite-Hat_Variant

[XFame]

Dieses Raetsel ist mir in der endlichen Variante mal untergekommen, ausserdem hat jeder Gefangene auch die Antworten seiner Vorgaenger gehoert. In diesem Fall stirbt hoechstens der erste Gefangene. Die Gefangenen waehlen naemlich folgende Strategie:

-Der erste Gefangene schaut sich die Huete aller Gefangenen vor sich an und sagt "rot", wenn er ungerade viele rote Huete sieht und "blau", wenn er gerade viele rote Huete sieht. Er kann damit natuerlich mit seiner Hutfarbe danebenliegen.

-Nun zaehlt der zweite Gefangene die Anzahl der roten Huete vor ihm. Ist diese gerade und sein Vorgaenger hat "rot" gesagt, so hat er selbst einen roten Hut auf. Er sagt nun "rot". Sieht er eine ungerade Anzahl von roten Hueten und sein Vorgaenger sagte "rot", so hat er einen blauen Hut auf. Genauso entscheidet er, falls der erste Gefangene "blau" sagte.

-Nun ist der dritte Gefangene dran. Wieder durch abzaehlen und den Antworten seiner Vorgaenger kann er seine Hutfarbe herausbekommen und sagt diese.

-usw. usf.

Im unendlichen Fall klappt das natuerlich nicht.