Problem med fanger og luer, hvis farge må bestemmes
Rekreasjon / / December 31, 2020
Det lukkende systemet ser alle hettene, men kan bare si "svart" eller "hvitt", samtidig som det informerer alle om den skjulte informasjonen. Fangene vet ikke det totale antallet svarte og hvite luer, det er mer enn to mulige alternativer. Men de er begrenset til bare to versjoner når det gjelder begrepet paritet: tallet kan være enten jevnt eller merkelig.
Nøkkelen til å løse problemet er dette: Fangene er enige om at den første responderen vil si, for eksempel "svart", hvis han ser et oddetall med svarte hatter foran, og "hvitt" hvis han ser et jevnt antall svarte caps.
La oss se på eksemplet fra bildet ovenfor. Den høyeste fangen nr. 1 ser tre svarte caps foran. Han snakker "svart" høyt. Dette gir alle andre informasjonen om at det er et oddetall med svarte caps foran. Den første fangen gjorde en feil med fargen på hetten, men dette er ikke skummelt: en gang er det lov å svare feil.
Fange nr. 2 ser et merkelig antall sorte caps foran seg. Hun innser at hun er hvit og svarer riktig. Fange nr. 3 ser et jevnt antall sorte luer og gjetter at han har på seg en svart lue som de to første fangene så.
Fange nr. 4 hører svaret og innser at hun burde se etter et jevnt antall svarte caps, fordi det var en svart bak ryggen hennes, men hun ser bare en foran og konkluderer med at hetten er svart. Fanger nr. 5-9 leter etter et oddetall av svarte caps, som de ser, mens de innser at de har hvite caps på. Turnen kommer til den tiende fangen. Hvis fange nr. 9 så et merkelig antall sorte luer, betyr dette bare én ting - fange nr. 10 har en svart lue.
Slik fungerer denne algoritmen for alle sett med hubcaps. For den første deltakeren er sannsynligheten for feil svar 50%, men informasjonen om jevn-paritet, som han vil gi, vil tillate resten av fangene å gjette fargen på hetten.
Hver respondent vil begynne å evaluere antall jevne og odde hender fremover. Hvis tallet som beregnes i hans sinn ikke sammenfaller med det han ser, så er hetten hans i samme farge. Hver gang i dette tilfellet tar den neste responderen i betraktning at jevnheten til de resterende capsene nå er endret.
Dette puslespillet er en oversettelse av en TED-Ed-video.