From Wikipedia, the free encyclopedia
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.
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:[1]
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.
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.[2]
Víťazná stratégia je následovná:[3]
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).
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:
číslo zásuvky | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
číslo väzňa | 7 | 4 | 6 | 8 | 1 | 3 | 5 | 2 |
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:
číslo zásuvky | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
číslo väzňa | 3 | 1 | 7 | 5 | 8 | 6 | 4 | 2 |
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í.
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 . V našom prípade je to teda bijektívna funkcia:
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.
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 , 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 . Existuje presne spôsobov, ako vybrať čísla, ktoré budú do tohoto cyklu patriť (viete z kombinatoriky). V rámci cyklu môžeme čísla usporiadať spôsobmi – čísla usporiadame spôsobmi, ale každé usporiadanie sa tam bude opakovať -krát, iba bude otočené – teda stále ten istý cyklus – platí: . Zvyšné čísla, nepatriace cyklu, usporiadame 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 je -té harmonické číslo .
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%![3]
Ak uvážime väzňov namiesto 100, kde je ľubovolné prirodzené číslo, pravdepodobnosť prežitia väzňov s cyklovou stratégiou je daná:
S Euler-Mascheroniovou konštantou pre
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.[3]
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.[2]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.