4. Gefangene und Hüte

Gefangene und Hüte

  • D

    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

    0
  • S

    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.

    0
  • C
    Mod

    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.

    0
  • ?

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

    0
  • J

    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 }

    0
  • ?

    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?

    0
  • J

    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.

    0
  • C
    Mod

    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.

    0
  • B

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

    0
  • X

    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.

    0
Anmelden zum Antworten