Problem dotyczący więźniów i czapek, których kolor należy określić
Rekreacja / / December 31, 2020
System zamykania widzi wszystkie kapsle, ale może powiedzieć tylko „czarny” lub „biały”, jednocześnie informując wszystkich o ukrytych informacjach. Więźniowie nie znają łącznej liczby czapek czarno-białych, są więcej niż dwie możliwości. Ale jeśli chodzi o koncepcję parzystości, są one ograniczone tylko do dwóch wersji: liczba może być parzysta lub nieparzysta.
Kluczem do rozwiązania problemu jest to: skazani zgadzają się, że pierwsza osoba udzielająca pomocy powie np. „Czarny”, jeśli widzi nieparzystą liczbę czarnych czapek z przodu i „białe”, jeśli widzi parzystą liczbę czarnych Czapki.
Spójrzmy na przykład z powyższego obrazka. Najwyższy więzień # 1 widzi przed sobą trzy czarne czapki. Mówi głośno „na czarno”. To daje wszystkim innym informację, że przed nami jest nieparzysta liczba czarnych kapsli. Pierwszy więzień pomylił się z kolorem czapki, ale to nie jest straszne: raz wolno mu odpowiedzieć nieprawidłowo.
Więzień # 2 widzi przed sobą nieparzystą liczbę czarnych czapek. Uświadamia sobie, że jest biała i odpowiada poprawnie. Więzień nr 3 widzi parzystą liczbę czarnych czapek i domyśla się, że ma na sobie czarną czapkę, którą widzieli pierwsi dwaj więźniowie.
Więzień nr 4 słyszy odpowiedź i zdaje sobie sprawę, że powinna rozejrzeć się za parzystą liczbą czarnych czapek, bo za jej plecami była czarna, ale widzi tylko jedną przed sobą i dochodzi do wniosku, że jej czapka jest czarna. Więźniowie nr 5-9 szukają nieparzystej liczby czarnych czapek, które widzą, zdając sobie sprawę, że mają na sobie białe czapki. Przyszła kolej na dziesiątego więźnia. Jeśli więzień nr 9 zobaczył nieparzystą liczbę czarnych czapek, oznacza to tylko jedno - więzień nr 10 ma czarną czapkę.
W ten sposób ten algorytm działałby dla dowolnego zestawu kołpaków. Dla pierwszego uczestnika prawdopodobieństwo błędnej odpowiedzi wynosi 50%, ale informacja o parzystych i nieparzystych parytetach, które poda, pozwoli pozostałym więźniom odgadnąć kolor czapki.
Każdy respondent zacznie szacować liczbę parzystych i nieparzystych limitów w przyszłości. Jeśli liczba obliczona w jego umyśle nie pokrywa się z tym, co widzi, to jego czapka jest tego samego koloru. Za każdym razem w tym przypadku kolejny respondent bierze pod uwagę, że parzystość pozostałych kapsli uległa zmianie.
Ta łamigłówka jest tłumaczeniem filmu TED-Ed.