Eberts Hutproblem

Eberts Hutproblem gehört zunächst in die Rubrik mathematischer Unterhaltungen und ist eines der zahlreichen Hutprobleme (engl. hat puzzles, oft auch prisoners and hat puzzles), bei denen einer Anzahl von Spielern zufällig verschiedenfarbige Hüte aufgesetzt werden und man die eigene Hutfarbe nicht kennt, aber erraten soll und damit in der Regel etwas gewinnen kann. Eberts Hutproblem ist insofern etwas Besonderes, als es Verbindungen zur Kodierungstheorie und zu fehlerkorrigierenden Codes, insbesondere zu Hamming-Codes, gibt. Mit Todd Eberts Dissertation ist dieses Problem 1998 bekannt geworden und z. B. auch in der Zeit und in Spektrum der Wissenschaft diskutiert worden.

Das Hutproblem mit drei Spielern

Das Spiel mit drei Spielern ist die bekannteste Variante. Die Spieler bekommen rein zufällig entweder einen roten oder einen blauen Hut aufgesetzt. Jeder Hutträger kann seine eigene Hutfarbe nicht erkennen. Die drei Spieler bilden ein Team und gewinnen, falls mindestens ein Spieler seine Hutfarbe richtig errät und keiner eine falsche Antwort gibt. Dabei darf jeder Spieler maximal einen Tipp abgeben und die Spieler dürfen untereinander keine Informationen austauschen. Jeder Spieler hat also nur drei Möglichkeiten: „Rot“ sagen, „Blau“ sagen oder schweigen. Eine naheliegende Strategie ist es, einen der Spieler zur Antwort zu verpflichten und die anderen schweigen zu lassen. Dieser eine Spieler wird dann mit der Wahrscheinlichkeit 50 % richtig antworten.

Allerdings kann das Team seine Gewinnwahrscheinlichkeit auf 75 % steigern, wenn jeder Spieler folgendermaßen entscheidet:

• Haben seine Mitspieler verschiedenfarbige Hüte, dann schweigt er.
• Haben sie gleichfarbige Hüte, dann nennt er die Hutfarbe, die seine Mitspieler nicht haben.

Es gibt insgesamt 8 mögliche Fälle der Hutverteilung auf die drei Köpfe, nämlich

$({\color {red}\bullet \bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet \bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet \bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet }{\color {blue}\bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet }{\color {red}\bullet \bullet })\quad ({\color {blue}\bullet \bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet }{\color {red}\bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet }{\color {blue}\bullet \bullet })$.

Nur in den beiden Fällen, dass alle die gleiche Hutfarbe tragen, ist die Antwort falsch, und dann antworten alle drei Spieler falsch. In den anderen sechs Fällen gibt genau ein Spieler die richtige Antwort, die anderen schweigen. Die Chance zu gewinnen liegt also bei 75 %. In den acht möglichen Fällen tippt jeder Spieler zweimal richtig und zweimal falsch. Der Clou dabei ist, dass sich die insgesamt sechs Falschantworten auf die zwei gleichfarbigen Fälle konzentrieren, während die sechs richtigen Antworten jeweils auf genau einen der weiteren sechs Fälle zutreffen. Die Team-Philosophie könnte man salopp so beschreiben: „Wenn schon verlieren, dann richtig. Gibt es im Team jemanden, der mehr weiß als du, dann schweige.“

Verallgemeinerung

Wenn die Anzahl der Spieler $n=2^{k}-1;\ k=2,3,\ldots \$ ist, dann kann das Team die Wahrscheinlichkeit des Verlierens auf $1/2^{k}$ reduzieren, im Fall $k=3$ bei $7$ Spielern also auf $1/8$. Um hier eine Strategie zu formulieren, sind Grundgedanken zu fehlerkorrigierenden Codes nötig.

Fehlerkorrigierende Codes

Siehe dazu auch die populärwissenschaftliche Einführung in. Eine Folge von $n$ Bits kann im Prinzip $2^{n}$ Nachrichten übermitteln, denn $2^{n}$ ist die Anzahl der Möglichkeiten, $n$ Nullen oder Einsen hintereinander zu schreiben. Wenn man Fehler erkennen bzw. korrigieren will, kann nicht jede dieser Bitfolgen eine Nachricht sein. Sei eine gewisse Bitfolge eine Nachricht, auch Codewort genannt. Die $n$ Bitfolgen, die sich vom Codewort an genau einer Stelle unterscheiden, heißen Fehlerwörter. Damit man Fehler korrigieren kann, darf ein solches Fehlerwort nicht zu mehreren Codewörtern gehören, d. h. jedes Codewort hat seine „eigenen“ $n$ Fehlerwörter. Von dem Vorrat der $2^{n}$ Bitfolgen verbraucht jedes Codewort $n+1$ Stück, eins für sich selber und $n$ für seine Fehlerwörter. Wenn $n+1$ selbst eine Zweierpotenz ist, können die Codewörter samt ihren Fehlerwörtern den Vorrat $2^{n}$ gerade restlos aufbrauchen. Daher kommt es, dass die Fälle $n=2^{k}-1$ besonders günstig zu behandeln sind. Beim fehlerkorrigierenden Code, den Richard Hamming im Jahr 1950 erfunden hat, korrigiert der Empfänger eine fehlerhafte Nachricht durch eine einfache Rechnung, die notfalls im Kopf durchgeführt werden kann.

Anwendung auf das Hutproblem

Die Spieler bekommen jeder eine Nummer von $1$ bis $n$, aber als Dualzahl dargestellt. In der Reihenfolge der Spieler werden die Hutfarben als Bitfolge interpretiert, eine Null für einen roten Hut, eine Eins für einen blauen. Jeder Spieler sieht die Bitfolge mit Ausnahme seines eigenen Bits. Das Team der Spieler einigt sich auf folgende Strategie: Sie glauben, dass die Bitfolge ihrer Hüte ein Fehlerwort ist. Das ist durchschnittlich in $n$ Fällen richtig und nur in einem Fall falsch. Wenn die Bitfolge tatsächlich ein Codewort ist, dann tippen alle $n$ Spieler falsch. Wenn die Bitfolge ein Fehlerwort ist, erkennt das genau einer der Spieler, und zwar der, der an der Position des Fehlers steht. Er erhält nämlich durch Einsetzen von Null oder Eins für seine eigene Hutfarbe einmal das Codewort und einmal das Fehlerwort und kann damit seine (Fehlerwort-)Hutfarbe richtig erraten. Die anderen Spieler an den Nicht-Fehler-Positionen erreichen durch Einsetzen von Null oder Eins beide Male Fehlerwörter und schweigen.

Beispiel Hutproblem mit 7 Spielern

Hier handelt es sich um den sogenannten $(7,4)$-Hamming-Code. Dabei steht die $7$ für die Bitfolgenlänge (bzw. Spieleranzahl) und durch $2^{7}=128$ für die Anzahl der dann möglichen Bitfolgen. Die $4$ steht durch $2^{4}=16$ für die Anzahl der Codewörter. Die folgenden $16$ Bitfolgen sind die Codewörter:

Codewörter
0000000	1000110	0100101	0010011	0001111	1100011	1010101	1001001
0110110	0101010	0011100	1110000	0111001	1101100	1011010	1111111

Dazu gibt es $16\cdot 7=112$ Fehlerwörter.

Für die sieben Spieler gibt es nun folgende Strategie: Jeder Spieler addiert (ohne Übertrag) die Dualzahlen der Spieler mit rotem Hut und erhält eine Prüfzahl $P$.

• Besteht für einen Spieler $P$ aus lauter Nullen, so antwortet er „Rot“.
• Ergibt für einen Spieler $P$ seine eigene Spielernummer, so antwortet er „Blau“.
• In allen anderen Fällen schweigen die Spieler.

Als Beispiel zur Berechnung sei nun der Fall betrachtet, in dem die Spieler mit den vorher vereinbarten Nummern $2$, $4$ und $5$ rote und die anderen blaue Hüte tragen. Dies entspricht dem Wort $1010011$. Jeder Spieler stellt nun fest, welche anderen Spieler rote Hüte tragen und bestimmt deren Nummern in Dualschreibweise. Spieler $1$ zum Beispiel (wie jeder andere Spieler mit blauem Hut auch) findet also die Spieler $2=010,4=100$ und $5=101$. Nun addiert er diese drei Zahlen ohne Übertrag oder anders ausgedrückt, er bestimmt für jede der drei Stellen einzeln, bei wie vielen der gefundenen Spieler an dieser Stelle eine $1$ steht. Ist diese Anzahl gerade, setzt er in $P$ an diese Stelle eine $0$, ist sie ungerade, eine $1$. An der ersten Stelle ist für die $4$ und die $5$ eine $1$, insgesamt also zwei. Somit beginnt $P$ mit einer $0$. An der zweiten Stelle hat nur die $2$ eine $1$, also auch $P$. An der dritten Stelle ist es nur die $5$. Für $P$ ergibt sich somit $011$. Zur Berechnung ist es also nicht notwendig, die Codewörter zu kennen.

Mit etwas Übung ist die Berechnung $010+100+101=110+101=011$ für die meisten bequemer, sie sollte jedoch nicht mit der „üblichen“ Addition (also der Addition mit Übertrag) verwechselt werden, wie das Ergebnis $2+4+5=3$ zeigt. Sie sollte auch nicht mit der Addition im Restklassenring modulo $8$ verwechselt werden, auch wenn das Ergebnis in diesem Beispiel gleich ist (siehe aber $2+4+6$).

Betrachten wir konkret zwei Fälle: Zuerst sei die Bitfolge der Hüte das Codewort $1010101$

Spielernummer	001	010	011	100	101	110	111
Codewort	1	0	1	0	1	0	1
Hutfarbe	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$
Prüfzahl $P$	010+100+110=000	100+110=010	000	010+110=100	000	010+100=110	000
Spielerantwort	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$

Alle Spieler haben falsch geantwortet. Das passiert mit Wahrscheinlichkeit $16/128=1/8$.

Sei nun die Bitfolge der Hüte das Fehlerwort $1010011$. Das ist übrigens ein Fehlerwort zum Codewort $0010011$, der Fehler liegt in der ersten Stelle.

Spielernummer	001	010	011	100	101	110	111
Fehlerwort	1	0	1	0	0	1	1
Hutfarbe	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {red}\bullet }$	${\color {red}\bullet }$	${\color {blue}\bullet }$	${\color {blue}\bullet }$
Prüfzahl $P$	010+100+101=011	100+101=001	011	010+101=111	010+100=110	011	011
Spielerantwort	Schweigen	Schweigen	${\color {blue}\bullet }$	Schweigen	Schweigen	Schweigen	Schweigen

Hier tippt, wie bei allen Fehlerwörtern, genau ein Spieler richtig.

Das Hutproblem für beliebige Spieleranzahl

Hier gibt es bislang keine optimale Verhaltensstrategie. Wenn $n\neq 2^{k}-1$, dann wäre es pragmatisch, nach dem Rezept für die nächstniedrigere Zweierpotenz zu spielen und sich damit die entsprechende Erfolgsrate zu sichern. Die überzähligen Spieler werden zum Schweigen verurteilt und deren Hutfarben werden nicht beachtet.