Krátko

Klobúky väzňov

Klobúky väzňov

30 väzňov je informovaných o tom, že budú umiestnení v rade a na hlavu každého z nich položia čiapku, bielu alebo čiernu, bez toho, aby uviedli, koľko klobúkov budú nosiť v každej farbe. Každý väzeň uvidí iba klobúky väzňov pred sebou, ale nie svojich alebo tých, ktorí sú za nimi.

Strážca požiada každého väzňa, ktorý sa začína postupne od posledného riadku (ktorý vidí všetko okrem jeho) až do prvého (kto nevidí nič), aká farba má jeho klobúk. Väzni môžu odpovedať iba na čiernu alebo bielu: ak uspejú, sú prepustení a ak nie, sú popravení. Všetci väzni môžu počuť odpovede pred ich. Väzni sa nemôžu dotýkať ostatných, ani sa ich dotýkať, ani dať náznak tónu alebo hlasu hlasu ... musia čo naj aseptickejším spôsobom odpovedať na čiernu alebo bielu, pretože ak väzni zistia akýkoľvek trik spomenutých, zabijú všetkých.

Predtým, ako to urobia, majú väzni, ktorí poznajú test, ktorému budú vystavení, ale nie prirodzene, akú farbu majú ich klobúky, čas na vzájomné rozhovory a premýšľanie o skupinovej stratégii.

Myslíte si, že existuje nejaká stratégia na záchranu čo najväčšieho počtu väzňov?

Riešenie

Je možné bezpečne zachrániť všetkých okrem posledného v rade, ktorí budú mať 50% šancu na záchranu.

Stratégia väzňov spočíva v „kodifikácii“ parity jednej z dvoch farieb klobúkov v rade. Napríklad sa môžu dohodnúť, že ten posledný v rade (kto ako prvý povie farbu svojho klobúku a nevie, čo to bude), bude hovoriť „biely“, ak je celkový počet bielych klobúkov, ktoré vidíte, párny alebo „čierny“ „Ak je celkový počet bielych klobúkov nepárny.

Predstavte si, že prvý vidí 25 bielych čiapiek, čo je párne číslo. Nevie, aká je jeho farba, takže si nemôže byť istý, čo musí povedať, aby sa zachránil, ale keďže množstvo bielych klobúkov, ktoré vidí, je nepárne a dosiahol dohodu so svojimi spoluhráčmi, hovorí „čierny“.

Druhý, ako počul „čierny“, vie, že celkový počet bielych viečok, ktoré prvý videl, je nepárny, takže ich počíta a ak vidí párne množstvo, jeho čiapka je biela a ak je čudná, jeho čiapka je čierna , Takže to hovorí.

Tretia strana vie, že pôvodne je množstvo nepárne (pretože prvá informácia je, že farba je čierna, inak by bola rovnomerná). Ak ten, ktorý pred ním povedal, povedal biely, počítajúc jeho, musí existovať rovnomerné množstvo, a ak povedal čierne, nepárne. Štúdiom parity tých, ktorých vidí, vie, aká je jeho farba. Čierna, ak sa vypočítané informácie zhodujú s tým, čo vidíte, inak biele.

Stručne povedané, informácia, že prvý vysiela, je parita počtu cieľov, ktoré vidí (čierna je nepárna, biela je párna). Každý musí zmeniť paritu z nepárnych na párne, keď jeden z väzňov, ktorého hovorí, hovorí „biely“ a spočítať tých, ktorých vidí. Ak sa parita, ktorú počíta, zhoduje s informáciami, ktoré mu boli poskytnuté, má klobúk čiernu a ak sa nezhoduje, je biela.

Neexistuje lepší systém, pretože neexistuje spôsob, ako by bývalý mohol poznať farbu svojho klobúka, takže bude mať 50% šancu na zlyhanie, postupujte podľa sledovanej stratégie.