Problém vězňů a čepic, jejichž barvu je třeba určit
Rekreace / / December 31, 2020
Uzavírací systém vidí všechny kryty, ale může říci pouze „černý“ nebo „bílý“, přičemž všechny současně informuje o skrytých informacích. Vězni neznají celkový počet černobílých čepic, existují více než dvě možnosti. Ale pokud jde o koncept parity, jsou omezeny pouze na dvě verze: počet může být sudý nebo lichý.
Klíčem k vyřešení problému je toto: vězni se shodují, že první respondent řekne například „černý“, pokud vidí lichý počet černých čepic vpředu, a „bílý“, pokud vidí sudý počet černých čepic čepice.
Podívejme se na příklad z obrázku výše. Nejvyšší vězeň # 1 vidí před sebou tři černé čepice. Nahlas mluví „černě“. To dává všem ostatním informaci, že před nimi je lichý počet černých čepic. První vězeň udělal chybu s barvou čepice, ale to je v pořádku: jednou je povoleno nesprávně odpovědět.
Vězeň # 2 vidí před sebou lichý počet černých čepic. Uvědomuje si, že je bílá a odpovídá správně. Vězeň # 3 vidí sudý počet černých čepic a odhaduje, že má na sobě černou čepici, kterou viděli první dva zajatci.
Zajatec č. 4 uslyší odpověď a uvědomí si, že by měla hledat sudý počet černých čepic, protože za jejími zády byla černá, ale ona vidí jen jednu vpředu a dospěla k závěru, že její čepice je černá. Vězni č. 5-9 hledají lichý počet černých čepic, které právě vidí, a zároveň si uvědomují, že mají bílé čepice. Na řadě je desátý vězeň. Pokud vězeň # 9 viděl lichý počet černých čepic, znamená to jen jednu věc - vězeň # 10 má černou čepici.
Takto by tento algoritmus fungoval pro jakoukoli sadu nábojnic. U prvního účastníka je pravděpodobnost nesprávné odpovědi 50%, ale informace o sudé-liché paritě, které uvede, umožní ostatním zajatcům uhodnout barvu jejich čepice.
Každý respondent začne vyhodnocovat počet sudých a lichých velkých písmen před sebou. Pokud se číslo vypočítané v jeho mysli neshoduje s tím, co vidí, pak má jeho čepice stejnou barvu. Pokaždé v tomto případě další respondér bere v úvahu, že sudá lichost zbývajících čepic se nyní změnila.
Tato hádanka je překladem videa TED-Ed.