Problem oko zatvorenika i kapa, čiju boju treba utvrditi
Rekreacija / / December 31, 2020
Sustav zatvaranja vidi sve kapice, ali može reći samo "crno" ili "bijelo", dok istovremeno obavještava sve o skrivenim informacijama. Zatvorenici ne znaju ukupan broj crno-bijelih kapa, postoje više od dvije mogućnosti. Ali oni su ograničeni na samo dvije verzije kada je riječ o konceptu pariteta: broj može biti paran ili neparan.
Ključ rješavanja problema je sljedeći: zatvorenici se slažu da će prvi reagirati reći, na primjer, "crno", ako sprijeda vidi neparan broj crnih kapa, a "bijelih" ako vidi parni broj crnih kapa kape.
Pogledajmo primjer sa gornje slike. Najviši zatvorenik # 1 vidi tri crne kape ispred sebe. Glasno kaže "crno". To svima drugima daje informaciju da je pred nama neparan broj crnih kapa. Prvi zatvorenik pogriješio je s bojom kapice, ali to je u redu: kad jednom dozvoli pogrešan odgovor.
Zatvorenik # 2 vidi neparan broj crnih kapa ispred sebe. Shvaća da je bijelka i točno odgovara. Zatvorenik br. 3 vidi paran broj crnih kapa i pretpostavlja da nosi crnu kapu koju su vidjela prva dva zarobljenika.
Zarobljenica br. 4 čuje odgovor i shvaća da bi trebala potražiti paran broj crnih kapa, jer joj je iza leđa bio crni, ali vidi samo jedan ispred i zaključuje da joj je kapa crna. Zatvorenici br. 5-9 traže neparan broj crnih kapa, koje upravo vide, a shvaćaju da nose bijele kape. Na red dolazi deseti zatvorenik. Ako je zatvorenik # 9 vidio neparan broj crnih kapa, to znači samo jedno - zatvorenik # 10 ima crnu kapu.
Ovako bi ovaj algoritam radio za bilo koji skup hubcapsa. Za prvog sudionika vjerojatnost netočnog odgovora iznosi 50%, ali informacije o parnom neparnom paritetu, koje će dati, omogućit će ostatku zarobljenika da pogodi boju svoje kape.
Svaki će ispitanik početi procjenjivati broj parnih i neparnih gornjih granica. Ako se broj izračunat u njegovom umu ne podudara s onim što vidi, tada je kapa iste boje. Svaki put u ovom slučaju, sljedeći odgovor uzima u obzir da se neparnost preostalih ograničenja sada promijenila.
Ova je zagonetka prijevod TED-Ed videa.