spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Da wir hier schon beim Rätseln sind, kommt hier noch eines meiner Lieblingsrätsel. Es ist ein reines Mathe-/Logikrätsel, die Geschichte dient nur als Dekoration, unmathematische Tricks funktionieren also nicht. Und obwohl wieder Wahrscheinlichkeiten vorkommen, verspreche ich, dass es nicht wieder in eine Diskussion über irgendwelche Verteilungen ausartet. Diesmal ist alles sauber definiert

"Ein böser Zauberer hält sich 100 Zwerge als Sklaven. Eines Tages beschließt er ihnen die Freiheit zu schenken, falls sie sein teuflisches Spiel gewinnen können (natürlich ist es nahezu unmöglich!). Jeder Zwerg bekommt entweder eine weiße oder eine schwarze Mütze aufgesetzt, dies entscheidet der Zauberer per Münzwurf (und er hat auf jeden Fall genügend Mützen). Dann kommen alle Zwerge in einen Raum, wo sie die Mütze jedes anderen Zwerges sehen können, ihre eigene jedoch nicht. Jetzt muss jeder Zwerg einen (geheimen) Tipp über seine Hut-Farbe abgeben. Haben alle Zwerge ihre Farbe korrekt geraten, gewinnen sie, hat sich auch nur einer vertan, verlieren sie das Spiel."

Die Regeln:
- Vor dem Spiel dürfen sich die Zwerge auf eine Strategie verständigen. Beispiele wären "Jeder tippt auf weiß", oder "Jeder tippt die Farbe, die sein rechter Nachbar nicht hat."
- Ist das Spiel gestartet, ist jegliche Kommunikation verboten. Die einzige Information, die die Zwerge haben, sind die Hutfarben von allen anderen Zwergen.
- Auch die Tipps sind den anderen Zwergen unbekannt.

Die Frage:
Mit welcher Strategie haben die Zwerge die maximale Chance zu gewinnen?


Hinweis: Raten alle Zwerge ohne jegliche Strategie, ist die Gewinnchance (0.5)^100, also für alle praktischen Belange gleich 0. Es gibt aber eine Strategie, die die Chancen enorm erhöht, und sie ist so einfach, dass sie jeder nachvollziehen kann. Ist halt nur echt kniffelig, drauf zu kommen

[Update:]
Ein Tipp / Hinweis: Kein Zwerg kann sich seiner Hut-Farbe sicher sein, da jegliche Kommunikation nach Spielstart verboten ist. Dennoch gibt es eine Strategie, die den Zwergen eine 50%ige Gewinnchance garantiert.
[/Update]

Zitat von »BlueCobold«

Binäres Insertion-Sort?

Strenggenommen ist das eine Form der Kommunikation zwischen den Zwergen ("Ich stell mich links / rechts von dir, abhängig von deiner Hut-Farbe"), und der böse Zauberer nimmt leider alles wirklich streng. Ist also leider nicht erlaubt, obwohl es eine sehr schlaue Idee ist.