Problem glede zapornikov in kapic, katerih barvo je treba določiti
Prosti čas / / December 31, 2020
Zapiralni sistem vidi vse zgornje meje, lahko pa izgovarja le "črno" ali "belo", hkrati pa obvestite vse o skritih informacijah. Zaporniki ne poznajo skupnega števila črno-belih kapic, obstajata več kot dve možnosti. Ko pa gre za koncept paritete, sta omejeni na le dve različici: število je lahko sodo ali liho.
Ključ rešitve problema je naslednji: zaporniki se strinjajo, da bo prvi odzivnik na primer rekel "črn" če spredaj zagleda neparno število črnih kapic in "bele", če vidi sodo število črnih kapic kapice.
Oglejmo si primer z zgornje slike. Najvišji zapornik št. 1 vidi tri črne kape pred seboj. Na glas reče »črno«. To vsem ostalim daje informacijo, da je pred nami neparno število črnih kapic. Prvi ujetnik se je zmotil z barvo pokrovčka, a to je v redu: ko je dovoljeno odgovoriti napačno.
Zapornica št. 2 zagleda pred seboj neparno število črnih kapic. Zaveda se, da je bela in pravilno odgovori. Zapornik št. 3 vidi sodo število črnih kapic in ugiba, da ima črno kapo, ki sta jo videla prva dva ujetnika.
Ujetnica št. 4 zasliši odgovor in se zaveda, da bi morala poiskati sodo število črnih kapic, ker je bila za njenim hrbtom črna, a spredaj vidi le eno in ugotovi, da je njena kapica črna. Zaporniki št. 5-9 iščejo neparno število črnih kapic, ki jih pravkar vidijo, hkrati pa se zavedajo, da nosijo bele kape. Na vrsto pride deseti zapornik. Če je zapornik št. 9 videl neparno število črnih kapic, pomeni samo eno stvar - zapornik št. 10 ima črno kapico.
Tako bo ta algoritem deloval za kateri koli niz hubcaps. Za prvega udeleženca je verjetnost napačnega odgovora 50%, vendar bodo informacije o sodo lih pariteti, ki jih bo dal, preostalim ujetnikom omogočile, da uganejo barvo svoje kapice.
Vsak anketiranec bo začel ocenjevati število sodo in liho zgornjo mejo naprej. Če število, izračunano v mislih, ne sovpada s tistim, kar vidi, je njegova kapica enake barve. Vsakič v tem primeru naslednji odzivnik upošteva, da se je zdaj spremenilo neparnost preostalih zgornjih mej.
Ta uganka je prevod videoposnetka TED-Ed.