Und noch ein Hutproblem...

Neue Frage »

Mystic Auf diesen Beitrag antworten »
Und noch ein Hutproblem...
Habe das Problem zwar in diesem Thread schon gestellt, doch passt es dort nicht hin, da es den Rahmen der Schulmathematik bei weitem sprengt und auch wahrscheinlichkeitstheoretische Betrachtungen eine eher untergeordnete Rolle spielen bzw. dann auch trivial sind...Ich hoffe daher, dass dieser Doppelpost ausnahmsweise akzeptiert wird...

Es geht also wieder mal um ein Hutproblem, das allerdings nur eine kleine Modifikation des obigen Hutproblems darstellt, wobei aus der Lösung, welche ad hoc nun sicher nicht mehr möglich ist, die eigentliche Grundidee, wie man so etwas löst, m.E. viel besser herauskommt...

Die Modifikation gegenüber obigem Hutproblem besteht darin, dass nun 7 (statt vorher 3) Leute einen roten bzw. blauen Hut aufgesetzt bekommen, wobei alle "Belegungen" gleichwahrscheinlich sind...

Zur Erinnerung:

- Jeder sieht zwar die Hüte aller anderen, aber nicht seinen eigenen
- Jeder versucht entweder die Farbe seines Hutes zu erraten oder er passt
- Das Team gewinnt, wenn mindestens einer richtig rät und keiner falsch
- Sie können sich zwar vorher eine gemeinsame Strategie zurechtlegen, aber nach dem Start des "Versuchs" erfolgt das Raten bzw. Passen gleichzeitig, d.h., ohne jede Art von Kommunikation oder Interaktion

Die Frage ist natürlich wieder: Was ist die beste Strategie für das Team und die Wahrscheinlichkeit des Gewinns bei ihrer Befolgung?

Edit: Wie immer, sollten sich Leser, welche die Lösung schon kennen, zunächst zurückhalten...
pandu1 Auf diesen Beitrag antworten »

Ich würde erstmal die gleiche Lösung vorschlagen: vier Teilnehmer passen, drei andere sehen sich gegenseitig an (wer was macht ist vorher abgesprochen). Jeder der zwei mal Rot sieht sagt Blau, jeder der zwei mal Blau sieht sagt Rot. Die Gewinnwarscheilichkeit ist 75%.
Mystic Auf diesen Beitrag antworten »

Ja, 75% Gewinnwahrscheinlichkeit ist schon mal nicht schlecht... Trotzdem läßt sich die Wahrscheinlichkeit zu verlieren, welche nach diesem Vorschlag 25% beträgt, durch die optimale Strategie noch halbieren...

Erstaunlicherweise hat die Lösung sehr viel mit dichtesten Kugelpackungen zu tun... Schauen wir uns dazu einfach noch einmal den Fall n=3, also von 3 Personen an, wo man alles noch ohne Mühe anschreiben kann... Indem wir jedem der drei Leute in bijektiver Weise eine Nummer aus {1,2,3} zuteilen und die Farben blau und rot mit 0 und 1 identifizieren, können wir die Menge der "Belegungen" mit Hüten durch die Menge S der 8 Tripel



darstellen, welche nach Voraussetzung alle gleichwahrscheinlich sein sollen...Wenn wir nun für alle x,y in S durch

d(x,y) = Anzahl der Positionen, an denn sich x und y unterscheiden

eine Metrik einführen, so können wir Kugeln mit Radius 1 um einen Punkt x in S durch



definieren...

Wir sehen dann z.B., dass die beiden Kugeln



und



eine dichteste Kugelpackung von S mit Kugeln vom Radius 1 darstellen, ja sogar eine 1-perfekte, da sie S zu 100% ausfüllen und sich dabei nicht überlappen... Auf dieser Tatsache baut nun die optimale Strategie des Teams auf, welche sich so beschreiben läßt:

Jeder Teilnehmer untersucht, ob aus seiner Sicht der Dinge das Tripel, welches der aktuellen Belegung entspricht, ein Kugelmittelpunkt, also 000 oder 111 sein könnte... Ist dies nicht der Fall (weil er zwei unterschiedliche Hutfarben sieht, womit eine Vervollständigung zu 000 oder 111 nicht mehr möglich ist!), so passt er, anderfalls rät er diejenige Hutfarbe, die das Tripel gerade nicht zu einem Kugelmittelpunkt vervollständigt... Die Idee dahinter: Es ist offensichtlich wahrscheinlicher, dass das aktuelle Tripel "am Rand" der Kugel und nicht gerade im Zentrum sitzt...Wir haben somit 3 günstige Fälle (Punkte am Rand) und 4 mögliche Fälle,d.h., die Erfolgswahrscheinlichkeit bei dieser Strategie ist 3/4...

Das ist sozusagen die "richtige" Sicht der Dinge, auch wenn sie anscheinend die Dinge verkompliziert, aber damit ist nun auch eine Verallgemeinerung auf den Fall von n=7 Personen möglich... Sieht vielleicht nun jemand, auf welche Weise?
Mystic Auf diesen Beitrag antworten »

Hier noch schnell der Vollständigkeit halber die Lösung des Hutproblems für n=7 Leute (wer diese selber finden finden möchte sollte also nun nicht weiterlesen!)...

Ich halte mich dabei weitgehend an die Bezeichnungen und Festlegungen, welche ich oben schon für n=3 eingeführt habe, alles wird nur etwas aufwändiger, geht aber im Prinzip genauso... Die Menge S aller Belegungen umfasst nun , also 128 Binärwörter und jeweils 8 entfallen auf jede Kugel vom Radius 1, z.B. ist



Dementsprechend können wir auf der Suche nach einer dichtesten Kugelpackung maximal 16 Kugeln mit Radius 1 finden, welche sich nicht überlappen... Unglaublich, aber wahr: Diese Maximalanzahl kann auch tatsächlich wieder erreicht werden, indem wir die Kugelmittelpunkte z.B. aus der nachfolgenden Liste von 16 Binärwörtern wählen:

0000000 1111111
1101000 0010111
0110100 1001011
0011010 1100101
0001101 1110010
1000110 0111001
0100011 1011100
1010001 0101110

Die optimale Stategie ist dann analog zum Fall n=3: Jeder Teilnehmer überprüft, ob er das gesuchte Binärwort, das der fraglichen Belegung mit Hüten entspricht, eines der 16 Worte aus obiger Liste sein könnte, indem er für das Bit, das ihm selbst zugeordnet ist, beide Möglichkeiten einsetzt...Wenn das nicht zutrifft (und das ist gewissermaßen der Normalfall!), dann sollte er passen, andernfalls sollte er die Farbe seines eigenen Hutes so raten, dass das entsprechende Binärwort gerade nicht in obiger Liste vorkommt... Diese Strategie ist natürlich dann goldrichtig, wenn das gesuchte Binärwort am Rand seiner Kugel liegt, was mit der Wahrscheinlichkeit 7/8 zutrifft und in diesem Fall würden alle bis auf einen passen, der dann auch richtig rät... Ist allerdings das gesuchte Binärwort ein Kugelmittelpunkt, d.h., aus obiger Liste von 16 Wörtern, so würden alle 7 Teilnehmer falsch raten...

Der letzte Satz ist auch der Schlüssel, um die hohe Erfolgswahrscheinlichkeit zu verstehen... Würde man nämlich den Versuch 8 mal durchführen, wobei einmal das fragliche Binärwort im Mittelpunkt seiner Kugel und 7 Mal an deren Rand liegt, so würden bei diesen 8 Versuchen insgesamt 14 Leute raten und zwar jeweils 7 falsch und 7 richtig... Diese 14 Leute haben also einzeln betrachtet eine fifty-fifty Chance richtig zu raten, genau wie dies unserer Logik entspricht, das gesamte Team aber hat gemäß unseren Regeln die unglaubliche Erfolgschance von 87.5% durch die ungleiche Verteilung der richtig bzw. falsch Ratenden auf diese 8 Versuche...

Zum Schluss noch: Sind die Teilnehmer nicht heillos überfordert, wenn sie sich obige Liste von 16 Binärwörter merken sollen? Nein, denn diese kann man sich bei näherer Betrachtung sogar sehr leicht merken... Wenn wir annehmen, dass sich alle gemäß ihrer Nummern im Kreis aufstellen, so muss dann nur jeder überprüfen, ob es (aus seiner Sicht!) das Binärwort 0000000 bzw. 1111111 sein könnte, oder ob es das Binärwört 1101 (restliche Bits 0) bzw. das Binärwort 0010 (restliche Bits 1) enthalten könnte, wenn man es zyklisch(!) liest... Zutreffendenfalls muss er wie oben angegeben raten, andernfalls passen...

Ja, wie die Experten hier wissen, gäbe es noch viel zu erzählen (z.B. wie man auf obige Liste von Kugelmittelpunkten überhaupt kommt!), aber das hier ist eh schon lang genug geworden und wer will kann ja z.B. unter den Stichworten Hammingcodes, zyklische Codes, perfekte Codes etc. ohnehin alles im Internet nachlesen... Wink

Edit: Übrigens gibt es auch noch sowas wie eine "Moral von der Geschichte", die ich mir nicht ganz verkneifen kann.... Angesichts der Tatsache, dass in 7 von 8 Fällen alle Teilnehmer passen zugunsten des einen, der beim Raten die größten Chancen hat, wird Behrlekamp in einem Artikel in der New York Times zitiert mit dem Ausspruch: "If the evidence suggests someone on your team knows more than you, you should keep your mouth shut"... Wie wahr! Die Welt sähe anders aus, würden sich alle daran halten... Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen