Das Hutproblem für
n=2k
- 1
Spieler
Die
Spieler werden von 1 bis n mit Dualzahlen durchnummeriert, d.h. z.B. im Fall von
7 Spielern (k=3)
001, 010, 011, ... , 111.
Blaue
Hüte werden mit 1, rote
Hüte mit 0 codiert.
Strategie
Jeder
Spieler „addiert“ die Dualzahlen der Spieler die einen roten Hut tragen.
(Die „Addition“ erfolgt allerdings ohne Übertrag!)
Dadurch
erhält er eine Prüfzahl P aus Nullen und Einsen.
Besteht
P aus lauter Nullen so antwortet er „rot“.
Ist
P gleich seiner eigenen Spielernummer so antwortet er „blau“.
In
allen anderen Fällen antwortet er nicht.
Theorie
Fallunterscheidung:
Fall
I.
Angenommen, die Summe aller Spieler mit einem roten Hut ist 00..0 :
S=n1 + n2 +...+nm
Dann
rechnet jeder Spieler mit einem blauen Hut P=00..0 aus, da er alle roten Hüte
sieht. Er antwortet deshalb
nach den Regeln der Strategie mit rot, d.h. falsch.
Betrachtet wird nun ein Spieler mit einem roten Hut und der Nummer ni.
Es ist S=n1 + n2 +...+ ni +...+nm = 0
Addition von ni auf beiden Seiten:
n1 + n2 +...+ (ni + ni) +...+ nm = ni
Da (ni + ni)=0 stellt die linke Seite die Prüfsumme dar welche dieser Spieler bildet.
Jeder
Spieler mit einem roten Hut rechnet
also seine eigene Spielernummer als Prüfsumme aus. Deshalb
antwortet er mit "blau" d.h. falsch.
Falls S=0 gilt, so antworten alle Spieler falsch!
Fall
II.
Die
Summe S aller Spielernummern die zu roten Hüten gehören ist ungleich 00..0.
Da die Spielernummern alle zwischen 1 und 2k - 1 liegen gibt es eine Spielernummer ni so dass S=ni gilt.
Jeder Spieler mit einem blauen Hut berechnet als seine Prüfsumme P diese Zahl ni da er alle roten Hüte sieht.
Kein Spieler mit einem roten Hut berechnet als Prüfsumme P seine eigene Nummer.
Begründung:
Falls P = ni gelten würde, so folgt:
P + ni = ni + ni = 0
Nun gilt für einen Spieler mit rotem Hut: S = P + ni .
Also: S = 0
Das ist aber ein Widerspruch zur Voraussetzung von Fall II.
Es gibt nun 2 Möglichkeiten:
1.
die Nummer ni gehört zu einem Spieler mit einem blauen Hut. Nach der Strategie rät dieser dann "blau", d.h. richtig.
Alle anderen Spieler antworten nicht,
die blauen nicht, weil es nicht ihre Nummer ist,
die roten können als Prüfzahl nicht 0 ermitteln.
Begründung:
Rechnet z.B Spieler nk seine Prüfziffer aus, so erhält er:
P=n1+...+ nm (Alle roten Platzziffern außer nk )
Addition von nk :
P+nk = S
Wäre P=0. so würde S=nk gelten, es ist aber S=ni .
2.
die Nummer ni gehört zu einem Spieler mit einem roten Hut.
Alle Spieler mit blauen Hüten schweigen da ni
- nicht ihre Nummer ist (keiner sagt deshalb blau) und
- jeder von ihnen rechnet P=S aus, was von 0 (nach Vor.) verschieden ist und deshalb antwortet niemand von ihnen mit rot.
Der Spieler mit der Nummer ni rechnet für seine Prüfzahl 0 aus:
S=n1 + n2 +...+ ni +...+nm = ni
Addition von ni auf beiden Seiten liefert:
n1 + n2 +...+ nm = 0
Die linke Seite ist aber gleich der Summe die der Spieler mit der Nummer ni ausrechnet (er sieht alle Hüte außer seinem eigenen), d.h. er antwortet mit "rot" und deshalb richtig.
Kein anderer Spieler mit einem roten Hut rechnet 0 als Prüfzahl aus:
S=n1 + n2 +...+ ni +...+nm = ni
Addition von nk liefert auf der linken Seite die Prüfzahl die der Spieler nk ausrechnet und rechts ni + nk .
ni + nk kann aber nicht 0 sein da ni sein eigenes additives Inverses ist.
Im Fall II wird demnach von genau einem Spieler richtig geantwortet.
Wie
oft kommen die Fälle I und II vor?
Die
Anzahl
der möglichen Summen beim Addieren aller Spielernummern ist 2k .
Jede dieser Summen tritt mit der gleichen Wahrscheinlichkeit auf.
00..0
ist eine von 2k Möglichkeiten.
Also ergibt sich ein Verlust mit der Wahrscheinlichkeit:
P(Verlust)=1/2k
Wahrscheinlichkeit für Gewinn:
P(Gewinn)=1-1/2k
Bsp.
1
k=2,
n=3, P(Verlust)=1/4, P(Gewinn)=3/4
Bsp.
2
k=4,
n=15, P(Verlust)=1/16,
P(Gewinn)=15/16.