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:

:*Riaditeľ väznice sa rozhodne dať poslednú šancu svojim 100 väzňom odsúdeným na smrť. Do svojej kancelárie, kde má 100 zásuviek (označených číslami 1 – 100) náhodne umiestni kartičky s číslami väzňov, ktorí sú tiež označení číslami 1 – 100. Väzni majú po jednom vchádzať do kancelárie. Každému dovolí otvoriť najviac 50 zásuviek. Z miestnosti odchádzajú inou chodbou, nemajú ako podať ďalším čakajúcim väzňom informácie. Riaditeľ väznice sa rozhodol, že *'omilostí všetkých** väzňov, ale iba **(práve) vtedy**, keď sa **každému** z väzňov **podarí nájsť svoje číslo** v jednej z 50 otvorených zásuviek. Ak čo len jeden z nich svoje číslo nenájde, všetci zomrú. Akú stratégiu majú väzni použiť, ak chcú mať čo najväčšiu šancu prežiť?''

== Riešenie ==

Ak každý väzeň otvorí 50 zásuviek [[Náhodnosť|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:

:<math>\underbrace{\left(\frac{1}{2}\right) \cdot \left(\frac{1}{2}\right) \cdot \ldots \cdot \left(\frac{1}{2}\right)}_{100 \times} = \left(\frac{1}{2}\right)^{100} \approx 0.0000000000000000000000000000008</math>

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á:

# Každý väzeň otvorí zásuvku, ktorá má jeho číslo.
# Ak táto zásuvka obsahuje jeho číslo, ukončí hľadanie a bol úspešný.
# V opačnom prípade zásuvka obsahuje číslo iného väzňa. Väzeň otvorí zásuvku s číslom toho iného väzňa.
# Väzeň opakuje kroky 2 a 3 až kým nenájde svoje číslo alebo otvorí 50 zásuviek.

Tento prístup zaručuje, že nebude otvárať zásuvky opakovane. Môžeme si všimnúť, že ak sa mu niekedy podarí &bdquo;uzavrieť cyklus&ldquo; – 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äzeň 1 otvorí zásuvku 1 a nájde čislo 7. Otvorí zásuvku 7 a nájde číslo 5. Otvorí zásuvku 5 a nájde číslo 1, teda jeho číslo, čiže uspel.
* Väzeň 2 otvorí zásuvky 2, 4 a 8 v tomto poradí. V poslednom nájde svoje číslo.
* Väzeň 3 otvorí zásuvky 3 a 6, kde nájde svoje číslo.
* Väzeň 4 otvorí zásuvky 4, 8 a 2, kde nájde svoje číslo. Všímavý čitateľ si mohol toto odvodiť z konanie väzňa 2. 
* Podobne aj väzni 5 až 8 nájdu svoje čísla (dá sa odvodiť z predchádzajúcich informácií).

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ácia (kombinatorika)|permutáciami]] čísel 1 až 100. Permutácie sú [[bijektívne zobrazenie|bijektívne zobrazenia]] (funkcie) z množiny prirodzených čísel <math>\mathbb{N}</math>.
V našom prípade je to teda bijektívna funkcia: <math>p: \{1, 2, \ldots, 100\} \to \{1, 2, \ldots, 100\}</math>

Intuitívne si funkciu permutácie predstavíme ako &bdquo;iné usporiadanie&ldquo; prvkov definičného oboru.

Každá permutácia sa dá rozložíť na tzv. [[permutácia (algebra)|cykly permutácie]] (postupnosť čísel, ktoré keď zobrazujem permutačnou funkciu sa eventuálne &bdquo;vráti&ldquo; do prvej hodnoty). Uvedomíme si, že tieto cykly sú vždy [[disjunktné množiny|disjunktné]] – nepretínajú sa, nemajú spoločné hodnoty. Permutáciu z prvého príkladu rozpíšeme v tzv. [[cyklová notácia|cyklovom zápise]] následovne:

:<math>(1 \,\,  7 \,\,  5) (2 \,\,  4 \,\,  8) (3 \,\,  6)</math>

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:

:<math>(1 \,\,  3 \,\,  7 \,\,  4 \,\,  5 \,\,  8 \,\,  2) (6)</math>

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: &bdquo;Zo všetkých permutácií na množine \{1, 2, \ldots, 100\}, koľko obsahuje cyklus s dĺžkou väčšou ako 50?&ldquo;
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 l > 50. Existuje presne \binom{100}{l} spôsobov, ako vybrať čísla, ktoré budú do tohoto cyklu patriť (viete z kombinatoriky). V rámci cyklu môžeme čísla usporiadať (l-1)! spôsobmi – čísla usporiadame l! spôsobmi, ale každé usporiadanie sa tam bude opakovať l-krát, iba bude otočené – teda stále ten istý cyklus – platí: \frac{l!}{l} = (l-1)!. Zvyšné čísla, nepatriace cyklu, usporiadame (100-l)! spôsobmi. Celkový počet vhodných permutácií je teda:

:\binom{100}{l} \cdot (l-1)! \cdot (100-l)! = \frac{100!}{l}

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):

:\frac{1}{100!} \left( \frac{100!}{51} + \ldots + \frac{100!}{100} \right) = \left( \frac{1}{51} + \ldots + \frac{1}{100} \right) = H_{100} - H_{50}

kde H_n je n-té harmonické číslo \left(H_n = \sum_{i=1}^{n} \frac{1}{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}\right).

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):

:1 - ( H_{100} - H_{50} ) \approx 0.31183

Väzni prežijú pomocou stratégie permutačných cyklov s pravdepodobnosťou väčšou než 30%!

### Asymptotika

Ak uvážime 2n väzňov namiesto 100, kde n \in \mathbb{N} je ľubovolné prirodzené číslo, pravdepodobnosť prežitia väzňov s cyklovou stratégiou je daná:

:1 - ( H_{2n} - H_n ) = 1 - (H_{2n} - \ln 2n) + (H_n - \ln n) - \ln 2

S Euler-Mascheroniovou konštantou \gamma pre n \to \infty

:\lim_{n \to \infty} (H_n - \ln n) = \gamma

platí, čo vedie k asymptotickej pravdepodbnosti prežitia:

:\lim_{n \to \infty} ( 1 - H_{2n} + H_n ) = 1 - \gamma + \gamma - \ln 2 = 1 - \ln 2 \approx 0.30685

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.

## Pozri aj
* Väzňova dilema
* Problém troch väzňov

## Referencie


## Literatúra

* 
* 
* 

## Externé odkazy
* Rob Heaton: Mathematicians hate civil liberties - 100 prisoners and 100 boxes, 13. januára 2014 
* Oliver Nash: Pity the prisoners , 12. decembra 2009 
* Jamie Mulholland: Prisoners in Boxes , jar 2011 (PDF) 
* MinutePhysics: An Impossible Bet a Solution to The Impossible Bet, 8. decembra 2014 

Kategória:Kombinatorika
Kategória:Pravdepodobnosť
Kategória:Matematické problémy