100 vangin ja 100 laatikon ongelma

100 vangin ja 100 laatikon ongelma on ongelma todennäköisyysteoriassa ja kombinatoriikassa . Tehtävän ydin on, että jokaisen 100 vangin on löydettävä numeronsa yhdestä sadasta laatikosta, jotta he kaikki selviävät; jos yksikin epäonnistuu, he kaikki kuolevat. Jokainen vanki saa avata vain 50 laatikkoa eikä voi kommunikoida muiden vankien kanssa, paitsi alustavan strategiakeskustelun vuoksi.

Ensi silmäyksellä tilanne näyttää toivottomalta, mutta on olemassa strategia, joka antaa vangeille noin 30 prosentin selviytymismahdollisuuden. Tanskalainen tietojenkäsittelytieteilijä Peter Miltersen ehdotti ongelmaa vuonna 2003 .

Kunto

Kirjallisuudessa ongelmalle on erilaisia ehtoja. Alla on Philippe Flajolet'n ja Robert Sedgwickin versio [1] .

Vankilan päällikkö tarjoaa sadalle kuolemaan tuomitulle vangille viimeisen mahdollisuuden. Vangit on numeroitu 1-100 ja huoneessa on vaatekaappi 100 vetolaatikolla. Pomo sijoittaa satunnaisesti yhden numeroista 1-100 jokaiseen ruutuun ja eri numerot kaikkiin ruutuihin. Vangit tulevat vuorotellen huoneeseen. Jokainen vanki voi avata ja tarkistaa 50 laatikkoa missä tahansa järjestyksessä. Jokaisen vangin jälkeen laatikot suljetaan uudelleen, ja kaikki numerot jäävät laatikoihin. Jos jokainen vanki löytää numeronsa yhdestä laatikosta, kaikki vangit saavat armahduksen; jos ainakin yksi vanki ei löydä numeroaan, kaikki vangit teloitetaan. Ennen kuin ensimmäinen vanki tulee huoneeseen, vangit voivat keskustella strategiasta, mutta eivät voi kommunikoida sen jälkeen. Mikä on paras strategia vangeille?

Oletetaan, että vankien lukumäärät jakautuvat laatikoiden kesken satunnaisesti, ja siksi kaikki laatikoissa olevien vankien lukumäärän permutaatiot ovat yhtä todennäköisiä. On myös selvää, että laatikot on myös numeroitu 1 - 100 tai tällaisen numeroinnin yksiselitteisyydestä voidaan sopia etukäteen.

Jos vanki valitsee satunnaisesti 50 laatikkoa 100 :sta , hänellä on 50 %:n mahdollisuus löytää numeronsa. Todennäköisyys, että kaikki vangit satunnaisia laatikoita avaamalla löytävät lukunsa, on yksittäisten vankien onnistumistodennäköisyyksien tulos, ts.

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

≈ 0,00000000000000000000000000000008

on häviävän pieni luku. Tilanne näyttää toivottomalta.

Ratkaisu

Strategia

On olemassa strategia, joka tarjoaa yli 30 %:n todennäköisyyden, että vangit selviävät hengissä. Menestyksen avain on, että vankien ei tarvitse päättää etukäteen, mitä laatikoita avaavat: jokainen voi käyttää jo avattujen laatikoiden sisällöstä saamiaan tietoja päättääkseen, kumman avaavat seuraavaksi. Toinen tärkeä havainto on, että yhden vangin menestys ei ole riippumaton muiden menestyksestä, koska ne kaikki riippuvat numeroiden sijoittelusta laatikoissa [2] .

Strategian kuvaamiseksi oletetaan, että paitsi vangit, myös laatikot on numeroitu 1-100 - esimerkiksi rivi riviltä alkaen vasemmasta yläruudusta. Strategia on [3] :

Jokainen vanki avaa ensin laatikon, jossa on numeronsa.
Jos tässä laatikossa on hänen numeronsa, vanki on onnistunut.
Muussa tapauksessa laatikko sisältää toisen vangin numeron, ja hän avaa laatikon tällä numerolla.
Vanki toistaa vaiheita 2 ja 3, kunnes hän löytää numeronsa tai avaa 50 laatikkoa.

Aloittaen omasta numerostaan ja käymällä silmukan läpi, vanki takaa olevansa laatikoiden sarjassa, joka päättyy hänen numeroonsa. Hänen toimiensa menestys riippuu vain siitä, onko tämä sarja pidempi kuin 50 laatikkoa.

Ongelman muokatussa versiossa, jossa on lisätty yksi hahmo - asianajaja, joka saa avata kaikki laatikot ja tarvittaessa vaihtaa kahden sisällön, vankien selviytymisestä tulee riippumaton alkuperäisestä permutaatiosta: tätä varten asianajaja, löydettyään yli 50 laatikkoa pidemmän syklin, katkaisee sen kahdeksi sykliksi, joiden pituus on enintään 50.

Esimerkkejä

Tämän strategian onnistumisen syytä voidaan havainnollistaa seuraavalla esimerkillä - vankeja ja laatikoita on 8, jokainen vanki voi avata 4 laatikkoa. Oletetaan, että vankilan päällikkö antoi vankien numerot laatikoihin seuraavasti:

laatikon numerot	yksi	2	3	neljä	5	6	7	kahdeksan
vankien numerot	7	neljä	6	kahdeksan	yksi	3	5	2

Yllä olevan strategian mukaan vangit toimivat seuraavasti:

Vanki 1 avaa ensin laatikon 1 ja löytää numeron 7. Sitten hän avaa laatikon 7 ja löytää numeron 5. Sitten hän avaa laatikon 5, josta hän löytää numeronsa ja siten onnistuu.
Vanki 2 avaa järjestyksessä laatikot 2, 4 ja 8. Viimeisestä laatikosta hän löytää numeronsa.
Vanki 3 avaa laatikot 3 ja 6; jälkimmäisestä hän löytää numeronsa.
Vanki 4 avaa laatikot 4, 8 ja 2 ennen kuin löytää numeronsa. Huomaa, että tämä on sama sykli, jonka Prisoner 2 kohtasi, vaikka kukaan näistä vangeista ei ole tietoinen siitä.
Myös 5–8-vuotiaat vangit löytävät numeronsa samalla tavalla.

Tässä esimerkissä kaikki vangit löytävät numeronsa, mutta näin ei aina ole. Jos esimerkiksi muutat laatikoiden 5 ja 8 sisältöä, vanki 1 käyttää kaikki yrityksensä avaamalla laatikot 1, 7, 5 ja 2, eikä löydä numeroaan:

laatikon numerot	yksi	2	3	neljä	5	6	7	kahdeksan
vankien numerot	7	neljä	6	kahdeksan	2	3	5	yksi

Ja seuraavassa järjestelyssä vanki 1 avaa laatikot 1, 3, 7 ja 4, eikä myöskään onnistu:

laatikon numerot	yksi	2	3	neljä	5	6	7	kahdeksan
vankien numerot	3	yksi	7	5	kahdeksan	6	neljä	2

Itse asiassa tässä esimerkissä kaikki paitsi 6 vankia eivät löydä laatikkoa numeroineen.

Selitys permutaatioiden suhteen

Vankien lukumäärien asettelu laatikoissa voidaan kuvata matemaattisesti lukujen permutaationa 1 - 100. Tällainen permutaatio on luonnollisten lukujen joukon 1 - 100 yksi-yhteen kartoitus itseensä. Numerosarjaa, jossa ensimmäinen siirtyy toiseen, toinen kolmanteen ja niin edelleen ja viimeinen ensimmäiseen, kutsutaan permutaatiosykliksi . Jokainen permutaatio voidaan hajottaa epäyhtenäisiksi sykleiksi, eli sykleiksi, joilla ei ole yhteisiä elementtejä. Yllä olevan ensimmäisen esimerkin permutaatio voidaan kirjoittaa silmukkamerkinnällä muodossa

{\näyttötyyli (1~7~5)(2~4~8)(3~6)}

ja koostuu siten kahdesta syklistä, joiden pituus on 3 ja yhdestä syklistä, jonka pituus on 2. Toisen esimerkin permutaatio on vastaavasti,

{\näyttötyyli (1~3~7~4~5~8~2)(6)}

ja se koostuu yhdestä syklistä, jonka pituus on 7, ja yhdestä syklistä, jonka pituus on 1.

Syklinen merkintätapa ei ole ainutlaatuinen, koska pituusjakso voidaan kirjoittaa monella eri tavalla riippuen ensimmäisen luvun valinnasta. Avaamalla laatikot yllä ehdotetun strategian mukaisesti jokainen vanki seuraa sykliä, joka päättyy omaan numeroonsa. Kahdeksan vangin tapauksessa tämä strategia onnistuu, jos ja vain, jos pisimmän permutaatiosyklin pituus on enintään 4. Jos permutaatio sisältää syklin, jonka pituus on 5 tai enemmän, kaikki vangit, joiden lukumäärä on sellaisessa syklissä, eivät saavuta niiden numero neljän askeleen jälkeen. $l$ $l$

Onnistumisen todennäköisyys

Alkuperäisessä tehtävässä 100 vankia onnistuu, jos pisin permutaatiosykli on korkeintaan 50. Siksi heidän eloonjäämistodennäköisyys on yhtä suuri kuin todennäköisyys, että satunnainen lukujen permutaatio 1:stä 100:aan ei sisällä pitempi sykliä kuin 50. Tämä todennäköisyys määritellään seuraavasti.

Numeroiden 1-100 permutaatio voi sisältää enintään yhden pituisen syklin . On olemassa tapoja valita numeroita sellaiselle syklille, jossa suluissa on yhdistelmiä . Nämä luvut voidaan järjestää syklin ympärille eri tavoilla, koska syklisen symmetrian vuoksi on olemassa tapoja kirjoittaa samanpituinen sykli . Loput numerot voidaan järjestää eri tavoilla. Yhteensä lukujen permutaatioiden määrä välillä 1 - 100 pituussyklillä on $l>50$ ${\tbinom {100}{l))$ ${\näyttötyyli (l-1)!}$ $l$ $l$ $(100-l)!$ $l>50$

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

Todennäköisyys, että ( tasaisesti jakautunut ) satunnainen permutaatio ei sisällä jaksoa, joka on pidempi kuin 50, lasketaan

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})\noin 0,31183

missä on harmoninen luku - . Siksi vangit selviävät hengissä noin 31 prosentissa tapauksista syklin seuraamisen strategiaa käyttäen [3] . Yllättäen tämä on yli 25% - vain kahden vangin onnistumisen todennäköisyys valita laatikot satunnaisesti ja itsenäisesti. $H n$ $n$

Asymptotiikka

Jos 100 vangin sijasta otetaan huomioon vangit, missä on mielivaltainen luonnollinen luku, vankien selviytymistodennäköisyys syklin seuraamisen strategiaa käytettäessä määritellään $2n$ $n$

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

Antaa olla Euler-Mascheronin vakio . Sitten saamme $\gamma$ $n\to\infty$

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

ja siksi eloonjäämisen todennäköisyydellä on taipumus

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

Koska todennäköisyyksien järjestys pienenee monotonisesti , syklin seuraamisen strategiaa käytettäessä vangit selviävät yli 30 %:ssa tapauksista vankien lukumäärästä riippumatta [3] .

Optimaalisuus

Vuonna 2006 Eugene Curtin ja Max Warsawer osoittivat syklin seuraamisen strategian optimaalisen. Todistus perustuu vastaavuuteen samanlaisen ongelman kanssa, jossa kaikki vangit saavat olla huoneessa ja katsella laatikoiden avaamista. Matemaattisesti tämä ekvivalenssi perustuu Foatan siirtymälemmaan , joka on yksi yhteen vastaavuus (kanonisen) syklisen merkinnän ja vakiopermutaatiomerkinnän välillä.[ määritä ] . Uudessa ongelmassa selviytymistodennäköisyys ei riipu valitusta strategiasta ja on yhtä suuri kuin alkuperäisen ongelman selviytymistodennäköisyys, kun käytetään syklin seuraamisen strategiaa. Koska alkuperäisen tehtävän mielivaltaista strategiaa voidaan soveltaa myös uuteen tehtävään, mutta sillä ei voida saavuttaa suurempaa selviytymistodennäköisyyttä, pyöräilystrategian on oltava optimaalinen [2] .

Historia

100 vankia ja 100 laatikkoa -ongelmaa pohti ensimmäisen kerran vuonna 2003 tanskalainen tietojenkäsittelytieteilijä Peter Miltersen, joka julkaisi sen yhdessä Anna Galin kanssa raportissaan 30. kansainvälisen automaatteja, kieliä ja ohjelmointia käsittelevän kollokvion tuloksista ( ICALP ). Pelaaja A (vankilan päällikkö) maalaa versiossaan satunnaisesti paperiliuskoja, joissa on B-joukkueen pelaajien (vankien) nimet, punaiseksi tai siniseksi ja asettaa jokaisen nauhan erilliseen laatikkoon, vaikka osa laatikoista saattaa olla tyhjiä. . Jotta joukkue B voittaisi, jokaisen sen jäsenen on nimettävä värinsä oikein avattuaan puolet laatikoista [4] .

Aluksi Milterson oletti, että voiton todennäköisyys menee nopeasti nollaan pelaajien määrän kasvaessa. Kuitenkin Sven Skyum, Miltersenin kollega Aarhusin yliopistosta , keksi pyöräilystrategian eräänlaiseen ongelmaan, jossa ei ole tyhjiä laatikoita. Tämän seurauksena artikkelissa tämän strategian löytäminen jätettiin harjoitukseksi. Artikkeli palkittiin[ selventää ] parhaan julkaisun palkinnot [2] .

Keväällä 2004 tämä ongelma ilmestyi Joe Buhlerin ja Alvin Berlekampin palapelisarakkeeseen The Mathematical Research Institute neljännesvuosittain [5] . Seuraavina vuosina tätä ongelmaa alettiin käyttää matemaattisessa kirjallisuudessa erilaisissa muotoiluissa - esimerkiksi korteilla pöydällä [6] tai lompakoilla kaapeissa [2] .

100 vankia ja 100 laatikkoa -tehtävän muodossa sen esittivät vuonna 2006 Christoph Peppe Spektrum der Wissenschaftissa ( Scientific Americanin saksankielinen versio ) [7] ja Peter Winkler College Mathematics Journalissa [8] . Pienillä muutoksilla tätä varianttia käyttivät Philippe Flajolet ja Robert Sedgwick [1] sekä Richard Stanley 3] kombinatoriikan oppikirjoissa .

Katso myös

Kolmen vangin tehtävä

Muistiinpanot

↑ 1 2 Philippe Flajolet, Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press, s. 124
↑ 1 2 3 4 Eugene Curtin, Max Warshauer (2006), Kaappipalapeli , Mathematical Intelligencer Vol . 28: 28–31 , DOI 10.1007/BF02986999
↑ 1 2 3 4 Richard P. Stanley (2013), Algebraic Combinatoriics: Walks, Trees, Tableaux, and More , Springer, s. 187-189
↑ Anna Gál, Peter Bro Miltersen (2003), Lyhyiden tietorakenteiden solukoetin monimutkaisuus, Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP) , s. 332-344
↑ Joe Buhler, Elwyn Berlekamp (2004), Puzzles Column , s. 3
↑ Richard E. Blahut (2014), Cryptography and Secure Communication , Cambridge University Press, s. 29–30
↑
↑ Peter Winkler (2006), Names in Boxes Puzzle , s. 260 285 289

Kirjallisuus

Philippe Flajolet , Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press
Richard P. Stanley (2013), Algebrallinen kombinatoriikka: kävelyt, puut, taulut ja paljon muuta , Springer
Peter Winkler (2007), Mathematical Mind-Benders , Taylor ja Francis