Home

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.

 

Beispiele zur Strategie

Simulation des Hutproblems

 

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 n 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+...+ n (Alle roten Platzziffern außer  n )

Addition von nk :

P+nk    = S

Wäre P=0. so würde S=n 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  n rechnet für seine Prüfzahl 0 aus:

S=n1 +  n2 +...+ ni +...+nm = n 

Addition von n auf beiden Seiten liefert: 

n1 +  n2 +...+ n = 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 = n 

Addition von n liefert auf der linken Seite die Prüfzahl die der Spieler n ausrechnet und rechts n + n

 n + n kann aber nicht 0 sein da  n 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.

Begründung

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.

 

Home