Problém 100 vězňů a 100 krabic

Problém 100 vězňů a 100 krabic je problémem teorie pravděpodobnosti a kombinatoriky . Podstatou úkolu je, že každý ze 100 vězňů musí najít své číslo v jedné ze 100 krabic, aby všichni přežili; pokud i jeden selže, všichni zemřou. Každý vězeň může otevřít pouze 50 krabic a nemůže komunikovat s ostatními vězni, s výjimkou předběžné diskuse o strategii.

Na první pohled vypadá situace beznadějně, ale existuje strategie, která dává vězňům šanci na přežití zhruba 30 %. Problém navrhl dánský počítačový vědec Peter Miltersen v roce 2003 .

Stav

V literatuře existují různé podmínky problému. Níže je uvedena verze Philippa Flajoleta a Roberta Sedgwicka [1] .

Šéf věznice nabízí stovce vězňů odsouzených k smrti poslední šanci. Vězni jsou očíslováni od 1 do 100 a místnost obsahuje skříň se 100 zásuvkami. Šéf náhodně umístí jedno z čísel od 1 do 100 do každého pole a jiná čísla do všech polí. Vězni se střídají ve vstupu do místnosti. Každý vězeň může otevřít a zaškrtnout 50 krabic v libovolném pořadí. Po každém vězni se krabice opět zavřou a všechna čísla zůstanou v krabicích. Pokud každý z vězňů najde své číslo v jedné z krabic, pak budou všichni vězni omilostněni; pokud alespoň jeden vězeň nenajde své číslo, budou všichni vězni popraveni. Než do místnosti vstoupí první vězeň, mohou vězni diskutovat o strategii, ale poté již nemohou komunikovat. Jaká je nejlepší strategie pro vězně?

Předpokládá se, že počty vězňů jsou mezi boxy rozmístěny náhodně, a proto jsou všechny permutace počtů vězňů v boxech stejně pravděpodobné. Rozumí se také, že krabice jsou také číslovány od 1 do 100, případně je možné se na jednoznačnosti takového číslování dohodnout předem.

Pokud si vězeň náhodně vybere 50 krabic ze 100 , má 50% šanci , že najde své číslo. Pravděpodobnost, že všichni vězni otevřením náhodných políček najdou svá čísla, je součinem pravděpodobností úspěchu jednotlivých vězňů, tzn.

\left({\frac {1}{2}}\right)^{100}

≈ 0,000000000000000000000000000008

je mizivě malé číslo. Situace se zdá být beznadějná.

Řešení

Strategie

Existuje strategie, která poskytuje více než 30% šanci, že vězni přežijí. Klíčem k úspěchu je, že vězni se nemusí předem rozhodovat, které krabice otevřou: každý se může na základě informací získaných z obsahu krabic, které již otevřel, rozhodnout, kterou otevře jako další. Dalším důležitým postřehem je, že úspěch jednoho vězně není nezávislý na úspěchu ostatních, protože všichni závisí na uspořádání čísel v polích [2] .

Pro popis strategie předpokládejme, že nejen vězni, ale i krabice jsou očíslovány od 1 do 100 – například řádek po řádku, počínaje od levého horního pole. Strategie je [3] :

Každý vězeň nejprve otevře krabici se svým číslem.
Pokud toto pole obsahuje jeho číslo, vězeň uspěl.
Jinak krabice obsahuje číslo dalšího vězně a ten otevře krabici s tímto číslem.
Vězeň opakuje kroky 2 a 3, dokud nenajde své číslo nebo neotevře 50 zásuvek.

Počínaje svým vlastním číslem a procházením smyčky vězeň zaručuje, že je v řadě políček končících jeho číslem. Úspěch jeho akcí závisí pouze na tom, zda je tato sekvence delší než 50 polí.

V upravené verzi problému, kde je přidána ještě jedna postava – právník, který smí otevřít všechny krabice a v případě potřeby prohodit obsah dvou z nich, se přežití vězňů stává nezávislým na počáteční permutaci: za tímto účelem právník, který objevil cyklus delší než 50 políček, jej přeruší na dva cykly o délce nepřesahující 50.

Příklady

Důvod úspěchu této strategie lze ilustrovat na následujícím příkladu – je zde 8 vězňů a krabic, každý vězeň může otevřít 4 krabice. Předpokládejme, že vedoucí věznice přiřadil čísla vězňů ke schránkám takto:

čísla krabic	jeden	2	3	čtyři	5	6	7	osm
čísla vězňů	7	čtyři	6	osm	jeden	3	5	2

Podle výše uvedené strategie se vězni chovají následovně:

Vězeň 1 nejprve otevře zásuvku 1 a najde číslo 7. Poté otevře zásuvku 7 a najde číslo 5. Poté otevře zásuvku 5, kde najde své číslo a tím uspěje.
Vězeň 2 postupně otevírá políčka 2, 4 a 8. V posledním poli najde své číslo.
Vězeň 3 otevírá zásuvky 3 a 6; v tom druhém najde své číslo.
Vězeň 4 otevře zásuvky 4, 8 a 2, než najde své číslo. Všimněte si, že se jedná o stejný cyklus, se kterým se setkal Vězeň 2, i když žádný z těchto vězňů si toho není vědom.
Podobným způsobem najdou svá čísla také vězni 5 až 8.

V tomto příkladu všichni vězni najdou svá čísla, ale není tomu tak vždy. Pokud například změníte obsah krabic 5 a 8, pak vězeň 1 využije všechny své pokusy otevřením krabic 1, 7, 5 a 2 a nenajde své číslo:

čísla krabic	jeden	2	3	čtyři	5	6	7	osm
čísla vězňů	7	čtyři	6	osm	2	3	5	jeden

A v následujícím uspořádání vězeň 1 otevře krabice 1, 3, 7 a 4 a také neuspěje:

čísla krabic	jeden	2	3	čtyři	5	6	7	osm
čísla vězňů	3	jeden	7	5	osm	6	čtyři	2

Ve skutečnosti v tomto příkladu všichni vězni kromě 6 nebudou moci najít krabici se svým číslem.

Vysvětlení z hlediska permutací

Rozložení počtu vězňů v krabicích lze matematicky popsat jako permutaci čísel od 1 do 100. Taková permutace je zobrazení množiny přirozených čísel od 1 do 100 jedna ku jedné na sebe. Posloupnost čísel taková, že první přejde na druhé, druhé na třetí atd. a poslední na první, se nazývá permutační cyklus . Každou permutaci lze rozložit na disjunktní cykly, tedy cykly, které nemají žádné společné prvky. Permutace z prvního příkladu výše může být zapsána ve smyčkové notaci jako

(1~7~5)(2~4~8)(3~6)

a skládá se tedy ze dvou cyklů délky 3 a jednoho cyklu délky 2. Permutace z druhého příkladu je, resp.

(1~3~7~4~5~8~2)(6)

a skládá se z jednoho cyklu o délce 7 a jednoho cyklu o délce 1.

Cyklický zápis není jedinečný, protože cyklus délky může být zapsán mnoha různými způsoby v závislosti na volbě prvního čísla. Otevíráním krabic podle výše navržené strategie se každý vězeň řídí cyklem, který končí jeho vlastním číslem. V případě osmi vězňů je tato strategie úspěšná právě tehdy, když délka nejdelšího permutačního cyklu je maximálně 4. Pokud permutace obsahuje cyklus o délce 5 a více, všichni vězni, jejichž počty leží v takovém cyklu, nedosahují jejich počet po čtyřech krocích. $l$ $l$

Pravděpodobnost úspěchu

V původním problému uspěje 100 vězňů, pokud nejdelší cyklus permutace bude maximálně 50. Pravděpodobnost jejich přežití se tedy rovná pravděpodobnosti, že náhodná permutace čísel od 1 do 100 neobsahuje cyklus o délce větší. než 50. Tato pravděpodobnost je definována následovně.

Permutace čísel od 1 do 100 může obsahovat nejvýše jeden cyklus délky . Existují způsoby, jak vybrat čísla pro takový cyklus, kde závorky označují kombinace . Tato čísla mohou být uspořádána kolem cyklu různými způsoby, protože kvůli cyklické symetrii existují způsoby, jak zapsat cyklus stejné délky . Zbývající čísla mohou být uspořádána různými způsoby. Celkem je počet permutací čísel od 1 do 100 s cyklem délky $l>50$ ${\tbinom {100}{l))$ $(l-1)!$ $l$ $l$ $(100-l)!$ $l>50$

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

Pravděpodobnost, že náhodná ( stejnoměrně distribuovaná ) permutace neobsahuje cyklus delší než 50, se vypočítá jako

1-{\frac {1}{100!)}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1 -\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\cca 0,31183

kde je -té harmonické číslo . Při použití strategie sledování cyklu tedy vězni přežívají asi ve 31 % případů [3] . Překvapivě je to více než 25 % – pravděpodobnost úspěchu pouze dvou vězňů, kteří si krabice vybírají náhodně a nezávisle. $H_n$ $n$

Asymptotika

Pokud místo 100 vězňů uvažujeme vězně, kde je libovolné přirozené číslo, pravděpodobnost přežití vězňů při použití strategie sledování cyklu je definována jako $2n$ $n$

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

Dovolit být Euler-Mascheroni konstanta . Pak jsme dostali $\gamma$ $n\to\infty$

\lim _{n\to \infty }(H_{n}-\ln n)=\gamma

a proto pravděpodobnost přežití má tendenci

\lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\cca 0,30685

Vzhledem k tomu, že sled pravděpodobností monotónně klesá , při použití strategie sledování cyklu přežívají vězni ve více než 30 % případů bez ohledu na počet vězňů [3] .

Optimality

V roce 2006 prokázali Eugene Curtin a Max Warsawer optimálnost strategie sledování cyklu. Důkaz je založen na ekvivalenci s podobným problémem, kdy všichni vězni mohou být přítomni v místnosti a sledovat otevírání boxů. Matematicky je tato ekvivalence založena na Foatově přechodovém lemmatu , korespondenci jedna ku jedné mezi (kanonickou) cyklickou notací a standardní permutační notací.[ specifikovat ] . V novém problému pravděpodobnost přežití nezávisí na zvolené strategii a rovná se pravděpodobnosti přežití v původním problému při použití strategie sledování cyklu. Vzhledem k tomu, že libovolnou strategii původního úkolu lze aplikovat i na nový úkol, ale nemůže dosáhnout vyšší pravděpodobnosti přežití, musí být strategie cyklování optimální [2] .

Historie

Problémem 100 vězňů a 100 krabic se poprvé zabýval v roce 2003 dánský počítačový vědec Peter Miltersen, který jej publikoval společně s Annou Gal ve zprávě o výsledcích 30. mezinárodního kolokvia o automatech, jazycích a programování ( ICALP ). V jejich verzi hráč A (vedoucí věznice) náhodně namaluje proužky papíru se jmény hráčů týmu B (vězňů) červenou nebo modrou a každý proužek umístí do samostatného pole, i když některé z polí mohou být prázdné. . Aby tým B vyhrál, musí každý jeho člen po otevření poloviny krabic správně pojmenovat svou barvu [4] .

Zpočátku Milterson předpokládal, že pravděpodobnost výhry rychle klesne na nulu s nárůstem počtu hráčů. Sven Skyum, kolega Miltersena z Aarhuské univerzity , však přišel s cyklistickou strategií pro jakýsi problém, který nemá prázdné krabice. Výsledkem bylo, že v článku bylo nalezení této strategie ponecháno jako cvičení. Článek byl oceněn[ upřesnit ] ocenění za nejlepší publikaci [2] .

Na jaře 2004 se tento problém objevil v hlavolamu Joe Buhlera a Alvina Berlekampa ve čtvrtletníku The Mathematical Research Institute [5] . V dalších letech se tento problém začal používat v matematické literatuře v různých formulacích - například s kartami na stole [6] nebo peněženkami ve skříňkách [2] .

V podobě problému 100 vězňů a 100 krabic jej předložili v roce 2006 Christoph Peppe ve Spektrum der Wissenschaft (německá verze Scientific American ) [7] a Peter Winkler v College Mathematics Journal [8] . S drobnými úpravami byla tato varianta použita v učebnicích kombinatoriky od Philippa Flajoleta a Roberta Sedgwicka [1] , jakož i od Richarda Stanleyho [3] .

Viz také

Úkol tří vězňů

Poznámky

↑ 1 2 Philippe Flajolet, Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press, s. 124
↑ 1 2 3 4 Eugene Curtin, Max Warshauer (2006), The locker puzzle , Mathematical Intelligencer Vol . 28: 28–31 , DOI 10.1007/BF02986999
↑ 1 2 3 4 Richard P. Stanley (2013), Algebraická kombinatorika: Procházky, stromy, výjevy a další , Springer, str. 187–189
↑ Anna Gál, Peter Bro Miltersen (2003), The cell probe complexity of succinct data structure, Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP) , s. 332–344
↑ Joe Buhler, Elwyn Berlekamp (2004), Puzzle Column , str. 3
↑ Richard E. Blahut (2014), Kryptografie a bezpečná komunikace , Cambridge University Press, s. 29–30
↑
↑ Peter Winkler (2006), Puzzle jmen v krabicích , str. 260,285,289

Literatura

Philippe Flajolet , Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press
Richard P. Stanley (2013), Algebraic Combinatorics: Walks, Trees, Tableaux, and More , Springer
Peter Winkler (2007), Mathematical Mind-Benders , Taylor a Francis