Problem mit Gefangenen und Mützen, deren Farbe bestimmt werden muss

Das Schließsystem sieht alle Kappen, kann jedoch nur "schwarz" oder "weiß" sagen und gleichzeitig alle über die verborgenen Informationen informieren. Die Gefangenen kennen nicht die Gesamtzahl der schwarzen und weißen Kappen, es gibt mehr als zwei mögliche Optionen. Beim Konzept der Parität sind sie jedoch auf nur zwei Versionen beschränkt: Die Zahl kann entweder gerade oder ungerade sein.

Der Schlüssel zur Lösung des Problems ist folgender: Die Gefangenen sind sich einig, dass der Ersthelfer beispielsweise "schwarz" sagt. wenn er eine ungerade Anzahl schwarzer Kappen vor sich sieht, und "weiß", wenn er eine gerade Anzahl schwarzer Kappen sieht Kappen.

Schauen wir uns das Beispiel aus dem obigen Bild an. Der größte Gefangene Nr. 1 sieht drei schwarze Kappen vor sich. Er sagt laut "schwarz". Dies gibt allen anderen die Information, dass eine ungerade Anzahl von schwarzen Kappen vor uns liegt. Der erste Gefangene hat einen Fehler mit der Farbe seiner Mütze gemacht, aber das ist keine große Sache: Sobald es erlaubt ist, falsch zu antworten.

Gefangene Nr. 2 sieht eine ungerade Anzahl schwarzer Mützen vor sich. Sie erkennt, dass sie weiß ist und antwortet richtig. Gefangener Nr. 3 sieht eine gerade Anzahl schwarzer Mützen und vermutet, dass er eine schwarze Mütze trägt, die die ersten beiden Gefangenen gesehen haben.

Gefangene Nr. 4 hört die Antwort und erkennt, dass sie nach einer geraden Anzahl schwarzer Kappen suchen sollte, da sich hinter ihrem Rücken eine schwarze befand, aber sie sieht nur eine vor sich und kommt zu dem Schluss, dass ihre Kappe schwarz ist. Die Gefangenen Nr. 5-9 suchen nach einer ungeraden Anzahl schwarzer Mützen, die sie gerade sehen, während sie feststellen, dass sie weiße Mützen tragen. Der zehnte Gefangene ist an der Reihe. Wenn Gefangener Nr. 9 eine ungerade Anzahl schwarzer Kappen gesehen hat, bedeutet dies nur eines: Gefangener Nr. 10 hat eine schwarze Kappe.

So funktioniert dieser Algorithmus für alle Hubcaps. Für den ersten Teilnehmer beträgt die Wahrscheinlichkeit einer falschen Antwort 50%, aber die Informationen über die ungerade Parität, die er geben wird, ermöglichen es dem Rest der Gefangenen, die Farbe ihrer Kappe zu erraten.

Jeder Befragte beginnt, die Anzahl der vor uns liegenden geraden und ungeraden Obergrenzen zu schätzen. Wenn die im Kopf berechnete Zahl nicht mit dem übereinstimmt, was er sieht, hat seine Kappe dieselbe Farbe. In diesem Fall berücksichtigt der nächste Antwortende jedes Mal, dass sich die Geradheit der verbleibenden Kappen geändert hat.

Dieses Puzzle ist eine Übersetzung eines TED-Ed-Videos.