Das Hüte-Rätsel verständlich erklärt

Drei Personen tragen je einen schwarzen oder weißen Hut, sehen die Hüte der anderen, nicht den eigenen, und tippen gleichzeitig auf die eigene Farbe oder passen. Mit der einfachsten Absprache gewinnt das Team die Hälfte der Fälle, mit einer klügeren drei von vier. Diese Seite zeigt, wie das geht und wo derselbe Trick wiederkehrt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Drei Personen, drei Hüte

Stellen Sie sich drei Personen vor. Jede bekommt einen Hut, schwarz oder weiß, per Münzwurf. Jede sieht die Hüte der beiden anderen, aber nicht den eigenen. Auf ein Zeichen sagt jede gleichzeitig „schwarz“, „weiß“ oder „ich passe“. Wer eine Farbe nennt, gibt einen Tipp für den eigenen Hut ab.

Das Team gewinnt, wenn mindestens eine Person tippt und alle, die tippen, richtig liegen. Liegt auch nur eine falsch, hat das Team verloren. Vorher dürfen sich die drei absprechen. Danach darf niemand mehr ein Wort sagen. Für die Hüte gibt es 8 mögliche Verteilungen, zum Beispiel schwarz, schwarz, weiß. Jede ist gleich wahrscheinlich.

Die einfachste Absprache: die Hälfte

Die einfachste Absprache: Eine Person tippt, die anderen beiden passen. Ihr Hut ist so oft schwarz wie weiß, also stimmt ihr Tipp in der Hälfte der Verteilungen. Das Team gewinnt damit die Hälfte aller Verteilungen.

Tippt dagegen jede Person „schwarz“, gewinnt das Team nur bei 1 von 8 Verteilungen. Sind die Hüte gemischt, liegt mindestens eine Person falsch, und ein einziger falscher Tipp genügt zum Verlieren.

Die klügere Absprache

Die drei können es besser. Sie wetten gemeinsam: „Die drei Hüte haben nicht alle dieselbe Farbe.“ Jede Person tippt so, als ginge die Wette auf. Sieht sie zwei gleiche Hüte, muss ihr eigener Hut nach der Wette die andere Farbe haben, also tippt sie die andere Farbe. Sieht sie zwei verschiedene Hüte, sagt die Wette nichts über ihren Hut, also passt sie. Die ganze Tabelle:

Hüte von Person 1, 2, 3	Tipps	Ergebnis
schwarz, schwarz, schwarz	alle drei: „weiß“	verloren
schwarz, schwarz, weiß	nur Person 3: „weiß“	gewonnen
schwarz, weiß, schwarz	nur Person 2: „weiß“	gewonnen
weiß, schwarz, schwarz	nur Person 1: „weiß“	gewonnen
weiß, weiß, schwarz	nur Person 3: „schwarz“	gewonnen
weiß, schwarz, weiß	nur Person 2: „schwarz“	gewonnen
schwarz, weiß, weiß	nur Person 1: „schwarz“	gewonnen
weiß, weiß, weiß	alle drei: „schwarz“	verloren

Stimmt die Wette, also bei zwei gleichen Hüten und einem abweichenden, tippt genau eine Person und liegt richtig. Das sind 6 von 8 Verteilungen. Bei drei gleichen Hüten stimmt die Wette nicht, alle drei tippen falsch: 2 von 8 Verteilungen. Das Team gewinnt also in 6 von 8 Verteilungen, das sind drei von vier.

Die Fehler werden gebündelt

Dabei wird nicht besser getippt. Jeder einzelne Tipp ist über alle 8 Verteilungen gezählt genauso oft richtig wie falsch: Wer die beiden anderen Hüte kennt, hat für den eigenen zwei gleich wahrscheinliche Möglichkeiten, und ein Tipp trifft genau eine davon. In der Tabelle stehen 6 richtige und 6 falsche Tipps. Alle 6 falschen stecken in den 2 verlorenen Verteilungen, jede gewonnene hat genau einen richtigen und keinen falschen. Die Absprache sammelt die Fehler dort, wo ohnehin verloren ist. Sie gehen nicht weg, sie werden dort verschwendet, wo sie nichts kosten.

Mehr als 6 von 8 geht mit keiner Absprache, in drei Schritten. Erstens sind richtige und falsche Tipps gleich viele. Zweitens hat jede gewonnene Verteilung mindestens einen richtigen und keinen falschen Tipp. Also gibt es höchstens so viele gewonnene Verteilungen wie falsche Tipps, und diese stecken alle in verlorenen Verteilungen. Drittens nimmt eine verlorene höchstens 3 falsche Tipps auf, einen je Person. Auf eine verlorene kommen daher höchstens 3 gewonnene, bei 8 Verteilungen also höchstens 6.

Zur Probe hat das Programm zum Ausprobieren alle Absprachen für drei Personen durchgespielt. Jede Person wählt für jede der vier möglichen Ansichten der beiden anderen Hüte „schwarz“, „weiß“ oder „ich passe“: drei Möglichkeiten an zwölf Stellen, zusammen 531.441 Absprachen. Keine gewinnt in mehr als 6 von 8 Verteilungen.

Derselbe Trick in anderer Kulisse

Der Trick: Das Team verabredet eine Prüfregel für alle Hüte, und jede Person tippt so, dass die Regel stimmt. Oben war es „nicht alle gleich“. Mit sieben Personen gibt es eine längere Regel nach demselben Muster, mit der das Team sieben von acht Verteilungen gewinnt. In den zwei folgenden Kulissen ist die Prüfregel eine Summe, die Prüfsumme.

Erstens: Personen stehen in einer Reihe und sehen nur die Hüte vor sich. Von hinten nach vorn tippt jede laut auf die eigene Farbe, alle hören alle Tipps. Die hinterste Person sagt „weiß“, wenn vor ihr eine ungerade Zahl weißer Hüte steht, sonst „schwarz“. Das ist die Prüfsumme; ihr eigener Tipp ist ein Glücksspiel.

Beispiel mit vier Personen: Die drei vorderen tragen weiß, schwarz, weiß, die hinterste sagt „schwarz“ (gerade Zahl). Die zweite sieht nur einen weißen Hut vor sich und braucht zur geraden Zahl noch einen: Sie tippt „weiß“. Die dritte sieht einen weißen Hut und hat die zweite „weiß“ tippen hören: schon zwei, also „schwarz“. Die vierte rechnet ebenso. Wenn alle fehlerfrei rechnen, liegen alle außer der hintersten richtig.

Zweitens: Auf jedem Feld eines Schachbretts liegt eine Münze, Kopf oder Zahl. Person A kennt ein Schlüsselfeld und muss genau eine Münze umdrehen. Person B sieht nur das Brett und soll das Schlüsselfeld nennen. Die Prüfsumme des Bretts rechnet die Nummern der Felder mit Kopf nach einer vereinbarten Regel zusammen. A dreht die Münze, die diese Summe genau auf die Nummer des Schlüsselfelds bringt. Bei 64 Feldern nennt so ein einziges umgedrehtes Feld jedes der 64 Felder.

Häufige Missverständnisse

• „Mit der Absprache tippt jede Person besser.“ Nein. Jeder Tipp ist so oft falsch wie richtig. Gewonnen wird durch das Zusammenspiel der Tipps.
• „Die Absprache mit der Prüfregel ist immer die beste.“ Nein. Bei zwei Farben und gleich wahrscheinlichen Hüten ist sie bei drei und bei sieben Personen nicht zu schlagen. Bei fünf Personen findet eine Rechnung der Demo eine bessere: 25 statt 24 von 32 Verteilungen. Bei sechs Personen auch.
• „Es genügt, dass jede Person irgendjemanden sieht.“ Nein. In den gemessenen Fällen mit höchstens fünf Personen, in denen keine drei einander alle sehen, schaffte die beste Absprache nur die Hälfte. Sehen sich drei einander alle, gewinnen sie mit der Wette von oben mindestens drei von vier.

Woran Sie das Muster erkennen

Anzeichen für diese Art von Aufgabe:

• Ein Team hat ein gemeinsames Ziel und darf sich vorab absprechen, danach aber nicht mehr verständigen.
• Jede Person sieht die Lage der anderen, aber nicht die eigene.
• Einzelne Fehler sind in Ordnung, wenn das Team gewinnt: Dann lohnt die Frage, ob sich die Fehler auf wenige Verteilungen bündeln lassen.

Wie ernst ist das Modell zu nehmen?

Es ist ein Rätsel mit gewählten Annahmen: Die Hutfarben sind gleich wahrscheinlich und unabhängig, die Absprache liegt vor dem Spiel, alle rechnen fehlerfrei. Die Zahlen sagen nichts über echte Menschen oder Geräte.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er behandelt vier Rätsel, in denen ein Team vorab eine Strategie vereinbart und danach nicht mehr kommuniziert. Gemeinsame Annahmen: Die Hutfarben sind gleichverteilt und unabhängig, die Strategien sind deterministisch (gemeinsamer Zufall ist nicht betrachtet), und alle Beteiligten rechnen fehlerfrei und kennen dieselbe Verabredung. Die Rätsel gelten als bekanntes Lehrbuchwissen; die Hamming-Strategie für drei und für sieben Hüte ist bekannt.

• Hüte gleichzeitig: \(n\) Spieler (2 bis 8) mit je einem Hut der Farbe 0 oder 1. Jeder sieht alle anderen Hüte, nicht den eigenen, und sagt gleichzeitig „0“, „1“ oder „passe“. Gewonnen ist, wenn mindestens einer rät und alle Rater richtig liegen. Es gibt \(2^n\) Hutverteilungen; \(W\) bezeichnet die Zahl der gewonnenen, \(L\) die der verlorenen, also \(W + L = 2^n\).
• Hüte in einer Reihe: \(n\) Personen (2 bis 12) mit je einem Hut aus \(q\) Farben (2 bis 6), nummeriert von hinten nach vorn; Person 1 steht ganz hinten. Person \(k\) sieht die Hüte \(h_{k+1}, \dots, h_n\) vor sich. Die Tipps fallen von hinten nach vorn laut, alle hören alle Tipps, erfahren aber nicht, ob sie stimmen. Gemessen wird die Zahl der richtigen Tipps.
• Summen-Hüte: \(n\) Spieler (1 bis 7, nummeriert ab 0; die Tabelle der App zählt ab 1) mit je einem Hut aus \(q\) Farben (2 bis 6). Jeder sieht alle anderen Hüte, alle tippen gleichzeitig auf den eigenen, ein Passen gibt es nicht. Gewonnen ist, wenn mindestens ein Tipp stimmt.
• Schachbrett: \(N = 2^t\) Felder (2 bis 64) mit je einer Münze, Kopf als 1 und Zahl als 0. A kennt das Schlüsselfeld \(z\) und dreht genau eine Münze um. B sieht nur das Brett und nennt \(z\).
• Sichtgraph: Bei den Hüten gleichzeitig sieht jeder Spieler nur seine Nachbarn in einem Graphen. Untersucht sind vier Formen (jeder sieht jeden, Ring, Kette, Stern) mit 3 bis 5 Spielern.
• Rechenweg: Hüte gleichzeitig und Summen-Hüte sind vollständig aufgezählt; die beste Strategie stammt aus einem vorgerechneten ganzzahligen Modell (HiGHS). In der Reihe sind bis zu 100 000 Verteilungen aufgezählt, darüber 5 000 zufällige. Das Brett ist bis 16 Felder vollständig geprüft, bei 32 und 64 Feldern mit 20 000 Zufallsfällen. Der Sichtgraph ist ein ganzzahliges Modell (CP-SAT, 20 s Zeitgrenze).

Die Formeln

Strategie und Verlustmenge. Eine Hutverteilung ist ein Punkt \(x \in \{0, 1\}^n\), zwei Verteilungen sind Nachbarn, wenn sie sich in einem Hut unterscheiden. Verliert das Team genau auf der Menge \(D\) der Verteilungen, so hat jede Verteilung außerhalb von \(D\) einen Nachbarn in \(D\): Der Spieler, der außerhalb von \(D\) richtig rät, sieht auf der Nachbarverteilung (nur sein Hut ist anders) dasselbe, rät dasselbe und liegt dort falsch. Umgekehrt gibt es zu jeder Menge \(D\) mit dieser Eigenschaft eine Strategie, die genau auf \(D\) verliert: Wer sieht, dass genau eine seiner zwei möglichen Verteilungen in \(D\) liegt, rät so, dass seine Verteilung außerhalb von \(D\) liegt, sonst passt er. Gesucht ist also eine kleinste Menge \(D\), bei der jede Verteilung in \(D\) liegt oder einen Nachbarn in \(D\) hat (ein Überdeckungscode vom Radius 1, anders gesagt eine kleinste dominierende Menge des Würfelgraphen). Die Gewinnzahl ist für jede solche Menge genau \(2^n - |D|\), am größten also bei einer kleinsten.

Obergrenze durch Zählen. Bei gleichverteilten Hüten ist jeder Tipp mit Wahrscheinlichkeit \(1/2\) richtig. Über alle \(2^n\) Verteilungen gibt es daher genauso viele richtige wie falsche Tipps. In einer gewonnenen Verteilung liegt mindestens ein Tipp richtig und keiner falsch, in einer verlorenen sind es höchstens \(n\) falsche. Mit \(W\) und \(L\) wie oben folgt

\[W \le \#\text{richtig} = \#\text{falsch} \le nL \quad\Rightarrow\quad \frac{W}{W+L} \le \frac{n}{n+1}\]

Ganzzahlig gilt \(W \le \lfloor n \cdot 2^n / (n+1) \rfloor\). Die Zahl \(\#\text{richtig}\) ist die Zahl der richtigen Tipps über alle Verteilungen, \(\#\text{falsch}\) die der falschen.

Hamming-Code. Sei \(m\) das größte \(2^r - 1\) mit \(m \le n\). Das Syndrom einer Verteilung \(x\) der ersten \(m\) Spieler (Position \(p\) = Spielernummer plus 1) ist \(s(x) = \bigoplus_{p:\, x_p = 1} p\); Codewörter haben \(s(x) = 0\), das sind \(2^{m-r}\) von \(2^m\). Spieler \(p\) betrachtet die zwei zu seiner Sicht passenden Verteilungen. Liegt genau eine im Code, tippt er so, dass seine Verteilung nicht im Code liegt, sonst passt er. Die übrigen \(n - m\) Spieler passen immer.

Reihe. Person 1 sagt \(a_1 = \sum_{j \ge 2} h_j \bmod q\) an. Person \(k \ge 2\) kennt \(a_1\), sieht \(h_{k+1}, \dots, h_n\) und hat \(a_2, \dots, a_{k-1}\) gehört. Sie tippt

\[a_k = a_1 - \sum_{j>k} h_j - \sum_{j=2}^{k-1} a_j \bmod q\]

Summen-Hüte. Spieler \(i\) bekommt die Zielsumme \(i \bmod q\) und tippt \(g_i = (i - \sum_{j \ne i} h_j) \bmod q\). Das ist richtig genau dann, wenn die Summe \(S = \sum_j h_j \bmod q\) aller Hüte gleich \(i \bmod q\) ist. Für alle \(n\) und \(q\) gilt als Grenze

\[P(\text{Gewinn}) \le \min\!\left(1,\ \frac{n}{q}\right)\]

Schachbrett. Für ein Brett \(b\) sei \(S(b) = \bigoplus_{f:\, b_f = 1} f\) das XOR der Nummern der Felder mit Kopf. Dreht man Feld \(f\), so gilt \(S(b \oplus e_f) = S(b) \oplus f\), wobei \(e_f\) das Brett ist, das nur auf Feld \(f\) eine 1 hat. A dreht Feld \(f = S(b) \oplus z\), danach ist \(S = z\), und B liest das Schlüsselfeld ab. Notwendig für eine perfekte Strategie auf \(N\) Feldern ist

\[|K| \cdot N = 2^N \quad\Rightarrow\quad N \mid 2^N\]

Dabei ist \(K\) eine Farbklasse, also die Menge der Bretter, bei denen B dasselbe Schlüsselfeld abliest. Die Herleitung steht unten.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen und durchgerechneten Beispiele sind Rechnungen dieser Seite, keine Messungen. Wo die Demo dieselbe Aussage prüft, steht es dabei.

Warum die Code-Strategie gewinnt (Hüte gleichzeitig).

• Schritt 1: Auf einem Nicht-Codewort \(x\) hat der Spieler \(p = s(x)\) die Eigenschaft, dass \(x \oplus e_p\) ein Codewort ist, denn \(s(x \oplus e_p) = s(x) \oplus p = 0\). Er sieht beide Verteilungen als möglich, genau eine ist im Code, also rät er die Farbe von \(x\) und liegt richtig.
• Schritt 2: Jeder andere Spieler \(p' \ne p\) sieht zwei Verteilungen mit Syndrom \(s(x)\) und \(s(x) \oplus p'\), beide ungleich null, und passt.
• Schritt 3: Auf einem Codewort sieht jeder der ersten \(m\) Spieler eine Verteilung im Code (die wahre) und eine außerhalb, rät also die falsche Farbe. Alle Rater liegen falsch, das Team verliert.
• Schritt 4: Verloren wird nur auf den Codewörtern, ein Anteil von \(2^{-r}\). Gewonnen wird in \(1 - 2^{-r} = m/(m+1)\) der Fälle, unabhängig davon, wie viele Spieler über \(m\) hinaus passen. Das ist genau die Obergrenze \(n/(n+1)\), wenn \(n = m\) ist: Der Code ist dann perfekt.

Durchgerechnet: \(n = 3\). Hier ist \(m = 3\), und der Code besteht aus den Verteilungen \((0, 0, 0)\) und \((1, 1, 1)\). Rechnung dieser Seite, die Tipps ergeben sich aus der Regel „bei zwei gleichen Hüten die andere Farbe, sonst passen“:

Verteilung \((h_1, h_2, h_3)\)	Tipps von Spieler 1, 2, 3	Ergebnis
\((0, 0, 0)\)	1, 1, 1	verloren, drei falsche Tipps
\((0, 0, 1)\)	passt, passt, 1	gewonnen
\((0, 1, 0)\)	passt, 1, passt	gewonnen
\((1, 0, 0)\)	1, passt, passt	gewonnen
\((0, 1, 1)\)	0, passt, passt	gewonnen
\((1, 0, 1)\)	passt, 0, passt	gewonnen
\((1, 1, 0)\)	passt, passt, 0	gewonnen
\((1, 1, 1)\)	0, 0, 0	verloren, drei falsche Tipps

Das sind 6 gewonnene Verteilungen mit je einem richtigen Tipp und 2 verlorene mit je drei falschen: 6 richtige und 6 falsche Tipps, wie das Zählargument verlangt. Hier gilt \(W = nL\) mit \(W = 6\) und \(L = 2\), die Obergrenze ist erreicht.

Weitere Größen. Bei \(n = 7\) hat der Code 16 Verteilungen von 128; \(W = 128 - 16\) und \(nL = 7 \cdot 16\) sind beide 112, die Obergrenze ist erreicht. Bei \(n = 5\) und 6 nutzt der Code nur drei Spieler und bleibt bei \(3/4\); bei \(n = 8\) nutzt er sieben, bleibt bei \(7/8\), und seine Gewinnzahl 224 liegt unter der Zählgrenze 227. Dass auch die beste Strategie bei \(n = 5, 6, 8\) darunter bleibt, zeigt der Löser, nicht das Zählargument.

Die Hüte in einer Reihe.

• Schritt 1: Person 1 sagt \(a_1 = \sum_{j \ge 2} h_j \bmod q\). Sie kann ihren eigenen Hut nicht kennen, ihr Tipp ist ein Glücksspiel.
• Schritt 2: Person \(k\) kennt \(a_1\), sieht die Hüte vor sich (\(h_{k+1}, \dots, h_n\)) und hat die Tipps \(a_2, \dots, a_{k-1}\) gehört. Waren diese richtig, sind es die Hüte \(h_2, \dots, h_{k-1}\). Dann ergibt die Formel \(a_1\) minus der Summe aller Hüte vor ihr minus der Summe \(h_2 + \dots + h_{k-1}\) gerade \(h_k\), denn \(a_1\) ist die Summe aller Hüte von \(h_2\) bis \(h_n\). Also ist \(a_k = h_k\).
• Schritt 3: Per Induktion sind alle Tipps der Personen 2 bis \(n\) richtig, auf jeder Hutverteilung. Im schlechtesten Fall liegt nur Person 1 falsch: \(n - 1\) richtige Tipps.
• Schritt 4: Zu jeder Sicht der Person 1 gibt es genau eine der \(q\) Farben, die ihr Tipp trifft. Sie liegt daher in einem Anteil \(1/q\) der Verteilungen richtig, und das Mittel der richtigen Tipps ist \(n - 1 + 1/q\).

Durchgerechnet: \(n = 4\), \(q = 3\). Rechnung dieser Seite, die Hüte sind \(h_1 = 0\), \(h_2 = 2\), \(h_3 = 1\), \(h_4 = 2\), alle Rechnungen modulo 3:

Person	Sieht	Hat gehört	Rechnung	Tipp	Eigener Hut
1	2, 1, 2	nichts	\(2 + 1 + 2 = 5 \equiv 2\)	2	0, also falsch
2	1, 2	\(a_1 = 2\)	\(2 - 1 - 2 = -1 \equiv 2\)	2	2, richtig
3	2	\(a_1 = 2\), \(a_2 = 2\)	\(2 - 2 - 2 = -2 \equiv 1\)	1	1, richtig
4	nichts	\(a_1 = 2\), \(a_2 = 2\), \(a_3 = 1\)	\(2 - 2 - 1 = -1 \equiv 2\)	2	2, richtig

Die Summen-Hüte.

• Schritt 1: Der Tipp \(g_i\) stimmt genau dann, wenn \(g_i = h_i\), also \(i - \sum_{j \ne i} h_j \equiv h_i\) und damit \(S \equiv i\) (modulo \(q\)).
• Schritt 2: Für \(n \ge q\) kommt jeder Rest modulo \(q\) als Zielsumme vor. Die Summe \(S\) hat irgendeinen Rest, also stimmt der Tipp des Spielers mit diesem Rest: mindestens ein Treffer in jeder Verteilung.
• Schritt 3: Für \(n = q\) gibt es zu jedem Rest genau einen Spieler, es stimmt also in jeder Verteilung genau ein Tipp.
• Schritt 4: Für \(n \le q\) ist jeder Tipp bei gleichverteilten Hüten mit Wahrscheinlichkeit \(1/q\) richtig, die erwartete Zahl richtiger Tipps ist \(n/q\). Weil in einer gewonnenen Verteilung mindestens ein Tipp stimmt, ist der Gewinnanteil höchstens \(n/q\). Die Summe erreicht das, denn die Ereignisse \(S \equiv i\) für verschiedene Zielsummen schließen sich aus.

Durchgerechnet: \(n = q = 2\). Rechnung dieser Seite. Spieler 0 hat die Zielsumme 0 und tippt \(g_0 = h_1\), Spieler 1 hat die Zielsumme 1 und tippt \(g_1 = (1 - h_0) \bmod 2\). Bei den Hüten \((h_0, h_1)\) gleich \((0, 0)\) und \((1, 1)\) stimmt nur der Tipp von Spieler 0, bei \((0, 1)\) und \((1, 0)\) nur der von Spieler 1: In jeder Verteilung stimmt genau ein Tipp.

Das Schachbrett.

• Schritt 1: Beim Umdrehen von Feld \(f\) kommt \(f\) in die Summe, wenn es vorher keinen Kopf trug, und fällt heraus, wenn es einen trug. Beides ist ein XOR mit \(f\), also \(S(b \oplus e_f) = S(b) \oplus f\).
• Schritt 2: A wählt \(f = S(b) \oplus z\). Dann ist \(S(b \oplus e_f) = S(b) \oplus S(b) \oplus z = z\).
• Schritt 3: \(f\) muss eine gültige Feldnummer sein. Bei \(N = 2^t\) sind die Nummern \(0, \dots, N-1\) genau die \(t\)-Bit-Zahlen, und das XOR zweier \(t\)-Bit-Zahlen ist wieder eine. Für andere \(N\) geht dieser Weg nicht.

Durchgerechnet: \(N = 4\). Rechnung dieser Seite. Köpfe liegen auf den Feldern 1 und 2, das Schlüsselfeld ist \(z = 0\). Dann ist \(S = 1 \oplus 2 = 3\). A dreht \(f = 3 \oplus 0 = 3\), nun liegen Köpfe auf 1, 2 und 3, und \(S = 1 \oplus 2 \oplus 3 = 0 = z\).

Warum nur Zweierpotenzen.

• Schritt 1: Eine perfekte Strategie färbt die \(2^N\) Bretter mit \(N\) Farben, wobei die Farbe das ist, was B abliest. A kann zu jedem Schlüsselfeld ein Brett erzeugen, das die gewünschte Farbe trägt. Also hat jedes Brett unter seinen \(N\) Nachbarn (je ein Feld gedreht) jede Farbe genau einmal.
• Schritt 2: Man zählt die Kanten zwischen einer Farbklasse \(K\) und allen Brettern. Jedes Brett hat genau einen Nachbarn in \(K\), das sind \(2^N\) Kanten. Jedes Brett aus \(K\) hat \(N\) Nachbarn, das sind \(|K| \cdot N\) Kanten.
• Schritt 3: Daraus folgt \(|K| \cdot N = 2^N\), also muss \(N\) ein Teiler von \(2^N\) sein. Das gilt genau für Zweierpotenzen.

Sichtgraph. Ein Dreieck, also drei Spieler, die einander alle sehen, spielt die Strategie für drei Hüte; alle anderen Spieler passen. Das gibt in jedem Graphen mit einem Dreieck mindestens \(3/4\) der Verteilungen (an einem Beispiel mit fünf Spielern gezählt: 24 von 32 Verteilungen). Dass es ohne Dreieck nicht mehr als die Hälfte gibt, ist nur in den gemessenen Fällen belegt, keine Herleitung.

Befunde

Alle Zahlen sind Aufzählungen oder Beweise, ausgenommen die genannten Stichproben (Brett mit 64 Feldern, die 17 Kombinationen der Reihe mit mehr als 100 000 Verteilungen) und mit dem Vorbehalt zur besten Strategie bei \(n = 8\) unter Grenzen. Jeder Wert gilt für die genannte Spielerzahl, zwei Farben bei den Hüten gleichzeitig und gleichverteilte Hüte.

Hüte gleichzeitig, \(n = 2\) bis 8. Angegeben ist die Zahl gewonnener Hutverteilungen. „Spieler im Code“ ist die Zahl der Spieler, die den Hamming-Code nutzen, die übrigen passen immer.

\(n\)	Verteilungen	Obergrenze	Code-Strategie	Beste Strategie	Spieler im Code
2	4	2	2	2	1
3	8	6	6	6	3
4	16	12	12	12	3
5	32	26	24	25	3
6	64	54	48	52	3
7	128	112	112	112	7
8	256	227	224	224	7

Der Code ist also nicht für alle Größen der beste: Bei \(n = 5\) gewinnt die beste Strategie 78,1 % der Verteilungen gegen 75,0 % der Code-Strategie, bei \(n = 6\) sind es 81,2 % gegen 75,0 %. Bei \(n = 2, 3, 4, 7, 8\) sind beide gleich. Die Obergrenze erreicht die beste Strategie bei \(n = 2, 3, 4, 7\), bei \(n = 5, 6, 8\) nicht. Der Anteil \(n/(n+1)\) selbst wird nur bei \(n = 2^r - 1\) genau getroffen, hier bei 3 und 7.

Frage	Befund
Gewinnt für drei Hüte irgendeine Strategie mehr als 75,0 %?	Nein. Von allen 531.441 Strategien (je Spieler und je Sicht von zwei Hüten „0“, „1“ oder „passe“, also \(3^{12}\)) gewinnt keine in mehr als 6 von 8 Verteilungen. Genau 4 Strategien erreichen das, 26.550 gewinnen mindestens 4 von 8. Zahl der Strategien nach Gewinnzahl 0 bis 8: 16.335; 120.736; 228.780; 139.040; 25.922; 624; 4; 0; 0.
Hüte in einer Reihe: wie viele sind sicher gerettet?	In allen 38 der 55 Kombinationen von \(n = 2\) bis 12 und \(q = 2\) bis 6, die aufgezählt werden (\(q^n \le 100.000\)), liegen mindestens \(n - 1\) Personen richtig, im Mittel genau \(n - 1 + 1/q\). Beispiel \(n = 12\), \(q = 2\) (alle 4.096 Verteilungen): mindestens 11, im Mittel 11,50 gegen 6,00 ohne Plan. Die erste Person liegt in einem Anteil \(1/q\) der Fälle richtig. Die übrigen 17 Kombinationen sind Stichproben von 5.000 Verteilungen; für sie gilt \(n - 1\) als Beweis, nicht als Messung.
Reihe: geht mehr?	Nein, für die kleinsten Fälle ausgezählt: Aus allen Strategien für \((n, q) = (2, 2)\), \((3, 2)\) und \((2, 3)\) ist der beste schlechteste Fall \(n - 1\) und das beste Mittel \(n - 1 + 1/q\).
Summen-Hüte: wie viele Tipps stimmen?	Bei \(n = q\) (\(q = 2\) bis 6) stimmt in allen \(q^q\) Verteilungen genau ein Tipp. Raten ohne Plan gewinnt bei \(q = n = 3\) nur in 70,4 % und bei \(q = n = 6\) in 66,5 % der Verteilungen (\(1 - (1 - 1/q)^n\); für wachsendes \(q\) bei \(n = q\) nähert sich das \(1 - 1/e = 63,2\) %). Bei \(n \ge q\) stimmt mindestens ein Tipp; bei \(n = 3\), \(q = 5\) gewinnt die Summe genau 75 von 125 = 60,0 %.
Ist \(n/q\) für Summen-Hüte eine Grenze?	Ja, bewiesen durch das Argument oben. Aus allen Strategien für \((n, q) = (1, 2)\), \((1, 3)\), \((2, 2)\), \((2, 3)\), \((2, 4)\) und \((3, 2)\) ist die beste Gewinnzahl \(\min(1, n/q) \cdot q^n\).
Schachbrett: stimmt die XOR-Strategie?	Für 2, 4, 8 und 16 Felder sind alle \(2^N\) Bretter mit allen \(N\) Schlüsselfeldern durchgespielt: 8, 64, 2.048 und 1.048.576 Fälle, kein Fehler. Für 64 Felder: 20.000 Zufallsfälle, kein Fehler, nicht aufgezählt; dass es immer gilt, folgt aus \(S(b \oplus e_f) = S(b) \oplus f\).
Gibt es das auch für 3 oder 6 Felder?	Nein. Aufgezählt: für \(N = 2\) gibt es 4 perfekte Strategien, für \(N = 3\) keine (alle 6.561 Färbungen geprüft). Das Zählargument lässt zwischen \(N = 2\) und 16 genau 2, 4, 8, 16 zu. Ein ganzzahliges Modell (CP-SAT) bestätigt für \(N = 2\) bis 7: möglich für 2 und 4, unmöglich für 3, 5, 6 und 7.
Wer sieht wen? (Beste Strategie, jeweils als optimal bewiesen)	Bei „jeder sieht jeden“: 6, 12, 25 Gewinnverteilungen von 8, 16, 32 für \(n = 3, 4, 5\). Im Ring 6, 8, 16 (bei \(n = 3\) ist der Ring ein Dreieck), in der Kette und im Stern für \(n = 3, 4, 5\) je 4, 8, 16. In allen 8 gemessenen Graphen ohne Dreieck ist der Optimalwert genau 1/2; mit einem Dreieck sind es mindestens 3/4.

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Tabelle für \(n = 2\) bis 7 samt der Beobachtung, dass der Code bei \(n = 5\) und 6 nicht der beste ist: aufgezählt, die beste Strategie für \(n \le 7\) in den Tests der Demo neu gelöst, für \(n \le 4\) zusätzlich durch Aufzählung aller Teilmengen.
• Die Aufzählung aller Strategien für drei Hüte und die Beweise der Obergrenzen und der Zweierpotenz-Bedingung.
• Die Reihe und die Summen-Hüte als Rechnung, für kleine Fälle zusätzlich durch Aufzählung aller Strategien.

Was sie nicht belegt, und die Grenzen:

• Annahmen: Gleichverteilte, unabhängige Hüte und die Gewinnregel „mindestens ein Rater, alle Rater richtig“. Bei anderer Verteilung oder anderer Gewinnregel (zum Beispiel: alle müssen raten) gelten die Zahlen nicht. Nach dem Hinweis der Demo kann dort etwa „alle raten die häufige Farbe“ besser sein als jeder Code; gerechnet ist das nicht.
• Zwei Farben: Bei den Hüten gleichzeitig sind nur zwei Farben gerechnet. Für mehr Farben gibt es nach der Zusammenfassung einer Arbeit (siehe Quellen) Überdeckungsverfahren; hier nicht gerechnet.
• Gemischte Strategien: Gemeinsamer Zufall ist eine Mischung deterministischer Strategien und kann den besten deterministischen Wert nicht übertreffen; die Demo zeigt ihn nicht.
• Optimalität bei 8 Spielern: Der Wert 224 für \(n = 8\) stammt aus dem Löser (Status „optimal“); die Optimalität ist bei \(n = 8\) nicht nachgerechnet, bei \(n \le 7\) schon. Die Obergrenze 227 ist bei \(n = 8\) nicht erreicht.
• Stichproben: Das 64-Felder-Brett (20 000 Fälle) und die 17 langen Reihen sind Stichproben; die Aussage folgt dort aus dem Beweis. Die vollständige Prüfung des Bretts geht nur bis 16 Felder.
• Sichtgraphen: Nur höchstens fünf Spieler und vier Formen. Ab sechs Spielern konnte der Löser in der Vormessung (Zeitgrenze 60 s, die App nutzt 20 s) die Optimalität meist nicht beweisen: bei 6 oder 7 Spielern gelang es nur in 1 von 8 Graphen. Aussagen für größere oder andere Graphen sind nicht gemessen.
• Modell: In der Reihe macht ein einziger Rechenfehler alle folgenden Tipps falsch (folgt aus der Formel, nicht gemessen). Nicht gerechnet sind der beste Erfolg auf Brettern ohne Zweierpotenz als Feldzahl, ungleiche Hutverteilungen und die Gewinnregel „alle raten“. Die Rätsel sind Modelle; Aussagen über Menschen gehören nicht dazu.

Quellen

• Lenstra, H. W.; Seroussi, G.: On Hats and other Covers, arXiv cs/0509045 (2005). Laut Zusammenfassung entsprechen bei zwei Farben die Strategien dem Überdeckungscode vom Radius 1; der Zusammenhang mit Hamming-Codes für \(n = 2^m - 1\) war schon vorher bekannt.
• Riis, S.: Information flows, graphs and their guessing numbers, Electronic Journal of Combinatorics 14 (2007), R44: Rateaufgaben auf Graphen.
• Die Hüte in der Reihe, die Summen-Hüte und das Schachbrett gelten als Sammlungswissen ohne einzelne Quelle.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Zu Lenstra und Seroussi liegt nur die Zusammenfassung vor, zu Riis nur Titel und bibliografische Angabe; dass dort alle Rater richtig liegen müssen, ist eine Erinnerung und nicht geprüft. Die Herkunft des Hüte-Rätsels bei Ebert (1998) steht nur in Sekundärquellen und wird nicht als geprüft ausgegeben. Die Tabelle für \(n = 2\) bis 8 ist selbst ausgezählt; ihre Werte sind in der Theorie der Überdeckungscodes vermutlich bekannt, Tabellen dazu wurden nicht eingesehen. Die Herleitungen und durchgerechneten Beispiele sind Rechnungen dieser Seite.