Behütete Gefangene      Teil 1


Freunde mathematischer Probleme kennen sicherlich die große Gruppe der "Farbige-Hüte-Probleme". In zahlreichen Variationen kommen darin Gefangene vor, denen eine Aufgabe gestellt wird, von deren erfolgreicher Lösung ihre Freilassung abhängt. Meist haben sie verschiedenfarbige Hüte auf, die jeder sehen kann, mit Ausnahme des eigenen Hutes. Die Kommunikation unter den Gefangenen ist auf eine einmalige Absprache unmittelbar nach der Bekanntgabe der Aufgabenstellung beschränkt.

Hier kommt ein einfaches Beispiel.

Zwei Gefangenen wird die folgende Situation vorgestellt. Beiden wird ein weißer oder schwarzer Hut aufgesetzt. Jeder kann nur die Hutfarbe des anderen sehen, soll aber seine eigene erraten, ohne dass die beiden Signale austauschen dürfen. Beide werden freigelassen, falls mindestens einer seine Hutfarbe richtig angibt. Vor dem Aufsetzen der Hüte dürfen sich die Gefangenen über ihre Strategie beraten.

Mit welcher Wahrscheinlichkeit werden die Gefangenen freigelassen, falls sie die optimale Strategie anwenden?

Lösung

Die Wahrscheinlichkeit ist  1 .

Eine (zunächst beliebig gewählte) von den Gefangenen A und B abgesprochene Strategie lässt sich beispielhaft tabellarisch darstellen:

Welche Strategie wird durch diese Tabelle dargestellt ?  A entscheidet sich immer für weiß, B entscheidet sich immer für die Farbe von A's Hut.  In den beiden ersten Spalten stehen alle Möglichkeiten für die tatsächlichen Hutfarben ( W  für weiß,  S  für schwarz), in den beiden Spalten daneben steht die Strategie. Rechts steht die Anzahl der Treffer. Die gewählte Strategie würde also die Gefangenen mit Wahrscheinlichkeit  p = 0.75  retten, da in der rechten Spalte genau eine  0  vorkommt.

Wir werden nun zeigen, dass sich die Gefangenen mit Sicherheit (also mit  p = 1 ) retten können. Das geht zur Not mit Ausprobieren von Einträgen in der 3. und 4. Spalte, aber es geht auch einfacher.

Das Ergebnis wird in der folgenden Tabelle festgehalten:

Diese Strategie lässt sich auch zahlentheoretisch formulieren. Man codiert  W  mit  0  und  S  mit  1 . Der Restklassenring  {0,1} = Z₂  erlaubt dann eine "Addition von Hutfarben" (man beachte  1 + 1 = 0 ). Die Verabredung der Gefangenen ist also: Beide wählen eine (voneinander verschiedene) Summe von Hutnummern  modulo 2  und nennen dann die dazu passende eigene Hutnummer. Genau einer wird recht haben (siehe Tabelle).

Publiziert 2013-12-27          Stand 2013-01-04

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem