Problém s väzňami a čiapkami, ktorých farbu je potrebné určiť

Uzatvárací systém vidí všetky viečka, ale môže povedať iba „čierny“ alebo „biely“, pričom súčasne informuje všetkých o skrytých informáciách. Väzni nepoznajú celkový počet čiernobielych čiapok, sú možné viac ako dve možnosti. Pokiaľ ide o koncept parity, sú obmedzené na iba dve verzie: počet môže byť párny alebo nepárny.

Kľúčom k vyriešeniu problému je tento: väzni súhlasia s tým, že prvý respondent povie napríklad „čierny“, ak vidí nepárny počet čiernych čiapok vpredu, a „biely“, ak vidí párny počet čiernych čiapok vrchnáky.

Pozrime sa na príklad z obrázku vyššie. Najvyšší väzeň # 1 vidí pred sebou tri čierne čiapky. Nahlas povie „čierny“. Toto dáva všetkým ostatným informácie, že pred nimi je nepárny počet čiernych čiapok. Prvý väzeň urobil chybu s farbou čiapky, ale nejde o veľkú chybu: ak bude mať dovolené odpovedať nesprávne, bude to mať chybu.

Väzeň č. 2 vidí pred sebou nepárny počet čiernych čiapok. Uvedomuje si, že je biela a odpovedá správne. Väzeň # 3 vidí párny počet čiernych čiapok a háda, že má na sebe čiernu čiapku, ktorú videli prví dvaja zajatci.

Zajatí č. 4 začuje odpoveď a uvedomuje si, že by mala hľadať párny počet čiernych čiapok, pretože za jej chrbtom bola čierna, ale dopredu vidí iba jednu a usudzuje, že jej čiapka je čierna. Väzni č. 5-9 hľadajú nepárny počet čiernych čiapok, ktoré práve vidia, a zároveň si uvedomujú, že majú biele čiapky. Na rade je desiaty väzeň. Ak uväznený č. 9 uvidel nepárny počet čiernych čiapok, znamená to iba jednu vec - väzeň č. 10 má čiernu čiapku.

Takto bude tento algoritmus fungovať pre každú sadu nábojov. Pre prvého účastníka je pravdepodobnosť nesprávnej odpovede 50%, ale informácie o párnej-nepárnej parite, ktoré uvedie, umožnia ostatným zajatcom uhádnuť farbu čiapky.

Každý respondent začne odhadovať počet párnych a nepárnych veľkých písmen dopredu. Ak sa počet vypočítaný v mysli nezhoduje s tým, čo vidí, potom má čiapka rovnakú farbu. Zakaždým, keď v tomto prípade ďalší respondent vezme do úvahy, že párna nepárnosť zostávajúcich veľkých písmen sa teraz zmenila.

Toto puzzle je prekladom videa TED-Ed.