Auf den ersten Blick scheint es eine ziemlich dämliche Rateshow zu sein. Drei Kandidaten werden ins Studio geleitet. Sowie einer von ihnen den Raum betritt, setzt die hübsche Assistentin des Quizmasters ihm einen Hut auf den Kopf, und zwar einen blauen oder einen roten, je nachdem, wie eine zuvor geworfene Münze fällt. Der Kandidat kann seinen Hut nicht sehen.

Nun stehen sie alle drei im Saal, und der Quizmaster sagt: "Schauen Sie sich die Hüte Ihrer Mitspieler genau an und raten Sie dann, welche Farbe Ihr eigener Hut hat. Sie dürfen sich nicht mit Ihren Mitspielern verständigen, und Sie hören auch deren Antworten nicht."

Was soll das? Die Farben der Hüte werden vollkommen unabhängig voneinander vom Zufall bestimmt. Also kann jeder Kandidat nichts weiter tun, als nach Belieben eine von beiden Farben anzusagen, mit einer Erfolgschance von 50 Prozent. Die Hüte der Mitspieler helfen ihm nicht bei der Entscheidung; er könnte ebenso gut die Augen schließen.

Aber der Quizmaster erläutert die Regeln weiter: "Sie drei sind ein Team; wenn Sie gewinnen, bekommt jeder von Ihnen 10000 Mark. Sie dürfen eine Farbe raten oder sich der Stimme enthalten. Zum Gewinnen genügt es, wenn eine richtige Antwort gegeben wird. Aber eine einzige falsche Antwort, und das Geld ist weg. Dasselbe gilt, wenn keiner von Ihnen etwas sagt."

Mit dieser Auskunft werden die Kandidaten in einen Nebenraum entlassen; das war nur die Generalprobe. Vor dem echten Spiel dürfen sie sich beraten; erst wenn es ernst wird, ist jede Verständigung unter ihnen unmöglich.

In der Strategiedebatte wird schnell klar: Man soll kein Wort zu viel sagen! Mehr als einer von ihnen sollte möglichst nicht den Mund aufmachen, denn jede weitere Antwort kann die Gewinnchancen nur verschlechtern. Die drei Glücksritter bestimmen durch Los denjenigen unter ihnen, der im entscheidenden Moment – "Welche Farbe hat Ihr Hut?" – die Antwort "blau" oder "rot" geben wird, es kommt nicht darauf an, welche; die beiden anderen werden eisern den Mund halten. So wahrt man immerhin eine Gewinnchance von 50 Prozent, und mehr kann man ohnehin nicht erreichen. Dies ist nicht das berühmte Ziegenproblem, bei dem der Quizmaster durch Öffnen einer falschen Tür eben doch gewisse Informationen preisgibt.

Die Argumentation scheint glasklar zu sein – und ist trotzdem falsch! Hier ist ein Rezept, mit dem die Gruppe eine Gewinnchance von stolzen 75 Prozent erreicht. Jeder schaut sich die Hüte seiner beiden Mitspieler an. Sind sie von verschiedener Farbe, so hält er den Mund. Sind sie gleichfarbig, dann behauptet er, sein Hut sei von der entgegengesetzten Farbe.

Wie kann das funktionieren? Man spiele sämtliche denkbaren Fälle durch. In zwei dieser acht Fälle sind alle Hüte von gleicher Farbe, und alle drei Kandidaten raten falsch. Aber in den sechs übrigen Fällen gibt es zwei Hüte von der einen und einen von der anderen Farbe, und dann liefert die Strategie die eine richtige Antwort, die man zum Gewinnen braucht.

Ist den Kandidaten auf magischem Wege doch höhere Erkenntnis über die Farbe des eigenen Hutes zuteil geworden? Keineswegs. Man betrachte für jeden Kandidaten die Fälle, in denen er überhaupt etwas sagt. In jeweils der Hälfte der Fälle sagt er "blau" oder "rot", und vor allem: in genau der Hälfte der Fälle das Falsche. Wie sollte es auch anders sein? Er weiß es ja nicht besser.

Die Strategie funktioniert nicht etwa, weil sie richtige Antworten gegenüber falschen begünstigen würde. Sie bewirkt vielmehr, dass die – unvermeidlichen – falschen Antworten sich auf wenige Fälle konzentrieren, wo sie entsprechend wenig Schaden anrichten. Eine falsche Antwort oder drei – das kostet dasselbe, nämlich den Sieg. Und in der Tat sind die beiden einzigen Fälle, in denen überhaupt falsch geraten wird, voll besetzt in dem Sinne, dass alle Beteiligten falsch raten. Sie packen also ihre unvermeidlichen Fehler auf zwei große Haufen, wo sie erheblich weniger stören, als wenn sie gleichmäßig verteilt wären.

Was passiert, wenn mehr als drei Mitspieler beteiligt sind? Wird dann nicht alles viel unübersichtlicher und die Gewinnchancen noch schlechter? Komplizierter wird es schon, aber die Gewinnchancen werden sogar noch besser. Sieben Beteiligte können in 7/8 aller Fälle gewinnen; fünfzehn Spieler verlieren nur in jedem sechzehnten Fall. Allgemein gilt: Wenn die Zahl der Spieler gleich 2^k–1 ist, also eins weniger ist als eine Zweierpotenz (3, 7, 15, 31, …), dann können sie ihre Verlustwahrscheinlichkeit bis auf 1/2^k reduzieren. Für andere Anzahlen sieht es nicht ganz so günstig aus. Immerhin können die Spieler nach dem Rezept für die nächstniedere Zweierpotenz spielen und die zugehörige Erfolgsrate erreichen, indem sie die überzähligen Spieler zum Schweigen verdonnern und deren Hüte nicht beachten.

Wie funktioniert das? Das sagt einem überraschenderweise ein Verfahren aus der Codierungstheorie. Es stammt aus den heroischen Frühzeiten der Informationstechnik, als man die Bits, jene kleinsten Informationseinheiten, die entweder eins oder null sind, noch einzeln über die Leitung rattern hören konnte und stets damit rechnen musste, dass ein Störsignal eine Eins in eine Null verwandelte oder umgekehrt. Heute sind die Übertragungsraten zwar um einige Zehnerpotenzen höher, aber Fehler kommen immer noch vor; deswegen werden der zu übertragenden Information Prüfbits beigemischt, Zusatzzeichen, an denen der Empfänger erkennen kann, ob unterwegs ein Bit umgekippt ist.

Noch bessere Verfahren erkennen nicht nur, dass ein Bit verfälscht worden ist, sondern auch, welches es war; sie können einen Fehler also nicht nur bemerken, sondern auch korrigieren. Diese Leistung erfordert einen Preis: Die Nachricht wird geschwätzig ("redundant"). Anders ausgedrückt: In eine Bitfolge gegebener Länge passt weniger Information, als eigentlich möglich wäre.

Eine Folge von n Bits kann im Prinzip 2^n verschiedene Nachrichten übermitteln, denn so viele verschiedene Möglichkeiten gibt es, n Nullen oder Einsen hintereinander zu schreiben. Wenn man aber Fehler erkennen oder gar korrigieren will, kann nicht jede dieser Bitfolgen eine Nachricht sein.

Erklären wir eine gewisse Folge von Bits zum Codewort, das heißt zu einer bedeutungstragenden Nachricht. Dann ist jede Bitfolge, die sich von dieser nur an einer Stelle unterscheidet, als Codewort nicht mehr brauchbar, denn sie könnte ja, für den Empfänger unentdeckbar, durch Verfälschung dieses Bits aus dem ursprünglichen Codewort hervorgegangen sein. Nennen wir sie ein Fehlerwort zu diesem Codewort. Wenn man Fehler auch korrigieren will, dürfen zwei Codewörter kein Fehlerwort gemeinsam haben. Nur dann kann nämlich der Empfänger ein Fehlerwort nicht nur als solches erkennen, sondern daraus auch das – dann eindeutige – richtige Codewort wiederherstellen.

Zu jedem Codewort gibt es n Fehlerwörter, eins für jede Bitposition; die Fehlerwörter sind also n-fach in der Überzahl. Von dem Vorrat der insgesamt 2^n verschiedenen Bitfolgen der Länge n verbraucht jedes Codewort n+1 Stück, eins für sich selbst und n Stück für seine Fehlerwörter. Wenn n+1 selbst eine Zweierpotenz ist, können die Codewörter samt ihrem "Hofstaat" an Fehlerwörtern den Vorrat der 2^n Wörter restlos aufbrauchen; daher kommt es, dass die Fälle n=2^k–1 besonders günstig auskommen.

Bei dem Fehler korrigierenden Code, den Richard W. Hamming (1915–1998), einer der Computerpioniere, 1948 erfunden hat, erkennt – und korrigiert – der Empfänger einzelne umgeklappte Bits durch eine einfache Rechnung, die zur Not im Kopf durchführbar ist.

Das ist wichtig für unsere Quizkandidaten. Die interpretieren jetzt nämlich die Folge der Hutfarben als Bitfolge: Sie bringen sich selbst in eine Reihenfolge und notieren in dieser Reihenfolge eine Null für einen roten Hut und eine Eins für einen blauen. Jeder Kandidat sieht diese Bitfolge, mit Ausnahme des einen Bits, das dem eigenen Hut entspricht.

In der Strategiebesprechung haben die Kandidaten sich darauf verständigt, daran zu glauben, dass die Bitfolge, die ihnen die Assistentin aufs Haupt drückt, nicht einem Codewort entspricht, sondern einem Fehlerwort. Das stimmt nicht immer, aber meistens, wegen der großen Überzahl der Fehlerwörter. Während des Spiels setzt jeder Mitspieler für seinen eigenen Hut probeweise die Werte 0 und 1 ein und rechnet aus, ob sich damit ein Codewort oder ein Fehlerwort ergibt. Wenn im einen Fall ein Codewort herauskommt und im anderen ein Fehlerwort, dann sagt er, seinem Glauben folgend, die Farbe an, die dem Fehlerwort entspricht. Wenn sich in beiden Fällen ein Fehlerwort ergibt, hält er den Mund. Es kann nicht in beiden Fällen ein Codewort entstehen, denn der Code ist so konstruiert, dass zwei Codewörter sich in mehr als einer Bitposition unterscheiden.

Warum ist diese Strategie so erfolgreich? Nehmen wir zuerst den seltenen Fall: Die Folge der Hutfarben ist ein Codewort. In diesem Falle sagen alle Spieler etwas, und zwar das Falsche; denn die richtige unter den beiden Möglichkeiten, die sie ausprobieren, verwerfen sie, weil sie einem Codewort entspricht.

Im weitaus häufigeren Fall ist jedoch die Folge der Hutfarben ein Fehlerwort. In diesem Fall gibt es genau eine Position, an der durch Umkippen des Bits ein Codewort entsteht. Der Spieler, der an dieser Position sitzt, erhält beim Durchprobieren ein Codewort sowie das originale Fehlerwort; da er sich für das Fehlerwort entscheidet, rät er richtig. Alle anderen aber schweigen, denn durch Ändern an der falschen Stelle wird aus einem Fehlerwort nur ein anderes Fehlerwort.

Im Endergebnis verlieren die Spieler im seltenen Fall und gewinnen im häufigen; und Gewinnen kommt n-mal so häufig vor wie Verlieren. Wie angenehm!

An dieser Stelle folgt unvermeidlich die Standardfrage: Sind diese Überlegungen zu irgendetwas nütze? Das Quiz selbst wohl kaum. "Wenn nur einer redet, hat er Recht; wenn sich alle einig sind, ist es falsch." Soll man diese Weisheit außerhalb des Spiels anwenden?

Aber die Hamming-Codierung ist selbstverständlich sehr nützlich. Sie und ihre Verwandten stecken tief in den Eingeweiden jedes Computers, und der Nutzer erlebt sie allenfalls als die Entdecker der schlechten Nachricht, dass diese Diskette nicht mehr lesbar ist. Ansonsten tun sie still und effizient ihren Dienst.

Es war auch eine ganz ernsthafte Untersuchung, die den Informatiker Todd Ebert auf die Ur-Idee brachte, als er an der Universität von Kalifornien in Santa Barbara an seiner Dissertation schrieb. Erst kürzlich, als er seinen Studenten das Problem in einer Verkleidung mit sieben Gefangenen und einem leicht sadistischen Wärter präsentierte (der Gewinn war nicht Geld, sondern die vorzeitige Entlassung), verbreitete sich der Gedanke über das Internet.

Aus: Spektrum der Wissenschaft 9 / 2001, Seite 100
© Spektrum der Wissenschaft Verlagsgesellschaft mbH