Problém 100 väzňov

Problém 100 väzňov je matematický problém z teórie pravdepodobnosti a kombinatoriky. Aby väzni prežili, musia všetci nájsť svoje vlastné číslo v jednej zo 100 zásuviek, pričom každý väzeň môže otvoriť iba 50 zásuviek a nemôže s ostatnými väzňami komunikovať. Na prvý pohľad vyzerá situácia beznádejná, ale existuje stratégia, ktorá dáva väzňom realistickú šancu na prežitie. Problém bol prvýkrát sformulovaný v roku 2003 dánskym informatikom Peter Bro Miltersenom.
Zadanie.
Problém 100 väzňov bol rôzne formulovaný rôznymi autormi. Nasledujúca verzia je voľným prekladom zadania podľa Phillippe Flajoleta a Roberta Sedgewicka:
Riešenie.
Ak každý väzeň otvorí 50 zásuviek náhodne, pravdepodobnosť, že jednotlivý väzeň nájde svoje číslo je 50%. Teda súhrnná pravdepodobnosť pre všetkých je súčin pravdepodobností jednotlivcov:
To je veľmi, veľmi malé číslo. Situácia vyzerá pre väzňov beznádejne.
Stratégia.
Prekvapivo, existuje stratégia, ktorá dáva väzňom šancu prežiť s viac než 30% pravdepodobnosťou. Dôležité je uvedomiť si, že väzňom nezáleží na tom, aby čo najviac z nich našlo svoje číslo, ale na tom, aby všetci našli svoje číslo.
Víťazná stratégia je následovná:
Tento prístup zaručuje, že nebude otvárať zásuvky opakovane. Môžeme si všimnúť, že ak sa mu niekedy podarí „uzavrieť cyklus“ – teda dostať sa naspäť do prvej otvorenej zásuvky, tak posledná otvorená zásuvka obsahuje jeho číslo (odkázala ho na zásuvku s jeho číslom, teda musela obsahovať jeho číslo).
Príklady.
Ukážeme si, že táto stratégia znie pre väzňov relatívne výhodne.
Uvážime zmenšenú situáciu s 8 väzňami a 8 zásuvkami, kde každý väzeň smie otvoriť 4 zásuvky. Riaditeľ rozmiestnil čísla do zásuviek následovne:
Väzni konajú následovne:
V tomto prípade všetci väzni boli úspešní. To sa však nestane vždy (na veľké sklamanie väzňov). Uvažujme nasledovné rozostavenie čísel riaditeľom:
V tomto prípade väzeň 1 otvorí zásuvky 1, 3, 7 a 4, otvorením ktorej musí skončiť, lebo nenašiel svoje číslo a viac ako 4 zásuvky otvoriť nemôže. Bol neúspešný, teda ďalší väzni už nemusia ani hrať, všetci budú popravení.
Reprezentácia permutáciami.
Riaditeľovo rozloženie čísel do zásuviek sa dá matematicky popísať permutáciami čísel 1 až 100. Permutácie sú bijektívne zobrazenia (funkcie) z množiny prirodzených čísel formula_2.
V našom prípade je to teda bijektívna funkcia: formula_3
Intuitívne si funkciu permutácie predstavíme ako „iné usporiadanie“ prvkov definičného oboru.
Každá permutácia sa dá rozložíť na tzv. cykly permutácie (postupnosť čísel, ktoré keď zobrazujem permutačnou funkciu sa eventuálne „vráti“ do prvej hodnoty). Uvedomíme si, že tieto cykly sú vždy disjunktné – nepretínajú sa, nemajú spoločné hodnoty. Permutáciu z prvého príkladu rozpíšeme v tzv. cyklovom zápise následovne:
Pozostáva teda z dvoch cyklov dĺžky 3 a jedného cyklu dĺžky 2. Permutáciu z príkladu 2 zapíšeme následovne:
Pozostáva z jedného cyklu dĺžky 7 a jedného cyklu dĺžky 1.
Uvedomíme si, že ak sa v cyklovom zápise rozostavení čísel do zásuviek nachádza cyklus dĺžky väčšej ako počet dovolených otvorení zásuviek, väzni (používajúc túto stratégiu) musia nutne prehrať -- ak by permutácia v už uvedených príkladoch mala cyklus dĺžky 5 a viac, všetci väzni, ktorých čísla sú v tomto cykle by prehrali po štyroch otvoreniach.
Pravdepodobnosť úspechu stratégie.
Vieme, že aj napriek stratégií môžu väzni prehrať. Majú však lepšiu šancu na výhru ako bez nej? Táto otázka sa dá zjednodušiť na otázku: „Zo všetkých permutácií na množine formula_6, koľko obsahuje cyklus s dĺžkou väčšou ako 50?“
Na túto otázku dokážeme už číselne odpovedať!
Uvedomíme si, že permutácia čísel 1 až 100 môže obsahovať najviac jeden cyklus s dĺžkou formula_7. Existuje presne formula_8 spôsobov, ako vybrať čísla, ktoré budú do tohoto cyklu patriť (viete z kombinatoriky). V rámci cyklu môžeme čísla usporiadať formula_9 spôsobmi – čísla usporiadame formula_10 spôsobmi, ale každé usporiadanie sa tam bude opakovať formula_11-krát, iba bude otočené – teda stále ten istý cyklus – platí: formula_12. Zvyšné čísla, nepatriace cyklu, usporiadame formula_13 spôsobmi. Celkový počet vhodných permutácií je teda:
Pravdepodobnosť, že náhodná permutácia obsahuje cyklus dĺžky väčšej ako 50 spočítame následovne (pomocou pravidla o nezávislých javoch):
kde formula_16 je formula_17-té harmonické číslo formula_18.
Pravdepodobnosť, že náhodná permutácia neobsahuje žiadny cyklus dĺžky väčšej ako 50 spočítame následovne (pomocou pravidla o opačnom jave):
Väzni prežijú pomocou stratégie permutačných cyklov s pravdepodobnosťou väčšou než 30%!
Asymptotika.
Ak uvážime formula_20 väzňov namiesto 100, kde formula_21 je ľubovolné prirodzené číslo, pravdepodobnosť prežitia väzňov s cyklovou stratégiou je daná:
S Euler-Mascheroniovou konštantou formula_23 pre formula_24
platí, čo vedie k asymptotickej pravdepodbnosti prežitia:
Postupnosť pravdepodobností je nerastúca (monotónna), pravdepodobnosť prežitia väzňov je väčšia ako 30%, nezávisle od počtu väzňov.
Optimalita.
V roku 2006, Eugene Curtin a Max Warshauer (z University of Texas) dodali dôkaz optimality tejto cyklovej stratégie. Dôkaz je založený na ekvivalencii s podobným problémom, kde väzni majú dovolené byť prítomní v miestnosti a pozorovať otváranie zásuviek inými väzňami. Táto ekvivalencia je založená na ekvivalencii cyklického zápisu a jednoriadkového zápisu permutácií (spodný riadok dvojriadkového zápisu).
V tomto probléme je nezávisle na stratégii pravdepodobnosť prežitia rovná pravdepodobnosti v pôvodnom probléme. Keďže ľubovolná stratégia z pôvodného problému sa dá aplikovať na pozmenený problém, ale nikdy nedosiahne väčšiu úspešnosť, musí byť cyklová stratégia optimálna.