Kalinių ir kepurių problema, kurios spalvą reikia nustatyti
Poilsis / / December 31, 2020
Uždarymo sistema mato visus dangtelius, tačiau gali pasakyti tik „juoda“ arba „balta“, tuo pat metu informuodama visus apie paslėptą informaciją. Kaliniai nežino viso juodų ir baltų kepurių skaičiaus, yra daugiau nei du variantai. Tačiau kalbant apie pariteto sąvoką, jie apsiriboja tik dviem versijomis: skaičius gali būti lyginis arba nelyginis.
Raktas sprendžiant šią problemą yra toks: kaliniai sutinka, kad pirmasis reaguojantis asmuo pasakys, pavyzdžiui, „juoda“, jei jis mato nelyginį skaičių juodų dangtelių priekyje, o „baltus“ - jei lyginį skaičių juodų dangtelių dangteliai.
Pažvelkime į pavyzdį iš paveikslėlio aukščiau. Aukščiausias kalinys Nr. 1 mato tris juodus dangtelius. Jis sako „juoda“ garsiai. Tai visiems kitiems suteikia informacijos, kad laukia nelyginis juodų dangtelių skaičius. Pirmasis kalinys padarė klaidą su dangtelio spalva, tačiau tai nėra baisu: kartą leidžiama atsakyti neteisingai.
Kalinė Nr. 2 mato priešais nelyginį skaičių juodų dangtelių. Ji supranta, kad yra balta, ir teisingai atsako. Kalinys Nr. 3 mato lyginį skaičių juodų kepurių ir spėja, kad jis dėvi juodą dangtelį, kurį matė du pirmieji belaisviai.
Nelaisvė Nr. 4 išgirsta atsakymą ir supranta, kad ji turėtų ieškoti lygių skaičių juodų dangtelių, nes už jos nugaros buvo juoda, tačiau ji mato tik vieną priekyje ir daro išvadą, kad jos dangtelis yra juodas. Kaliniai Nr. 5-9 ieško nelyginio skaičiaus juodų dangtelių, kuriuos jie tiesiog mato, suprasdami, kad jie dėvi baltus kepurėlius. Eilė ateina į dešimtąjį kalinį. Jei kalinys Nr. 9 matė nelyginį skaičių juodų dangtelių, tai reiškia tik vieną dalyką - kalinys Nr. 10 turi juodą dangtelį.
Tai, kaip šis algoritmas veiks bet kuriam „hubcaps“ rinkiniui. Pirmajam dalyviui neteisingo atsakymo tikimybė yra 50%, tačiau informacija apie lyginį-nelyginį paritetą, kurį jis pateiks, leis likusiems belaisviams atspėti jų dangtelio spalvą.
Kiekvienas respondentas pradės vertinti laukiančių lyginių ir nelyginių viršutinių ribų skaičių. Jei mintyse apskaičiuotas skaičius nesutampa su tuo, ką jis mato, tada jo dangtelis yra tos pačios spalvos. Kiekvieną kartą šiuo atveju kitas atsakantis asmuo atsižvelgia į tai, kad likusių kepurių tolygumas dabar pasikeitė.
Šis galvosūkis yra „TED-Ed“ vaizdo įrašo vertimas.