100 fogoly és 100 doboz problémája

A 100 fogoly és 100 doboz probléma a valószínűségszámítás és a kombinatorika területén . A feladat lényege, hogy a 100 rab mindegyikének meg kell találnia a számát a 100 doboz valamelyikében, hogy életben maradjon; ha csak egy is elbukik, mind meghalnak. Minden fogoly csak 50 dobozt nyithat ki, és nem kommunikálhat más foglyokkal, kivéve a stratégia előzetes megbeszélését.

Első pillantásra a helyzet reménytelennek tűnik, de van egy stratégia, amely körülbelül 30%-os túlélési esélyt ad a foglyoknak. A problémát Peter Miltersen dán informatikus javasolta 2003 - ban .

Állapot

A szakirodalomban a probléma különböző feltételei vannak. Alább Philippe Flajolet és Robert Sedgwick verziója [1] .

A börtön vezetője száz halálra ítélt rabnak kínál egy utolsó esélyt. A foglyok 1-től 100-ig vannak számozva, és a szobában 100 fiókos szekrény található. A főnök véletlenszerűen elhelyez egy számot 1-től 100-ig minden mezőbe, és különböző számokat minden mezőbe. A foglyok felváltva lépnek be a szobába. Minden fogoly 50 dobozt nyithat fel és ellenőrizhet bármilyen sorrendben. Minden fogoly után a dobozokat újra bezárják, és az összes szám a dobozokban marad. Ha mindegyik fogoly megtalálja a számát az egyik dobozban, akkor minden fogoly kegyelmet kap; ha legalább egy rab nem találja meg a számát, az összes rabot kivégzik. Mielőtt az első fogoly belépne a szobába, a foglyok megbeszélhetik a stratégiát, de ezt követően nem tudnak kommunikálni. Mi a legjobb stratégia a foglyok számára?

Feltételezzük, hogy a foglyok száma véletlenszerűen oszlik el a dobozok között, ezért a dobozokban lévő foglyok számának minden permutációja egyformán valószínű. Az is érthető, hogy a rovatokat 1-től 100-ig is számozzák, vagy előre meg lehet állapodni az ilyen számozás egyértelműségében.

Ha egy fogoly véletlenszerűen választ 50 dobozt a 100 -ból , akkor 50%-os eséllyel találja meg a számát. Annak a valószínűsége, hogy a véletlenszerű dobozok kinyitásával az összes fogoly megtalálja a számát, az egyes rabok sikerességi valószínűségének szorzata, azaz.

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

≈ 0.0000000000000000000000000000008

eltűnően csekély szám. A helyzet reménytelennek tűnik.

Megoldás

Stratégia

Létezik olyan stratégia, amely több mint 30%-os esélyt biztosít a foglyok életben maradására. A siker kulcsa, hogy a fogvatartottaknak nem kell előre eldönteniük, melyik dobozt nyissák ki: a már kinyitott dobozok tartalmából szerzett információk alapján mindenki eldöntheti, melyiket nyitja ki legközelebb. Egy másik fontos megfigyelés, hogy egy fogoly sikere nem független a többiek sikerétől, hiszen mindegyik a négyzetekben lévő számok elrendezésétől függ [2] .

A stratégia leírásához tegyük fel, hogy nemcsak a foglyokat, hanem a dobozokat is számozzuk 1-től 100-ig – például soronként, a bal felső doboztól kezdve. A stratégia a következő [3] :

Minden fogoly először kinyitja a számával ellátott dobozt.
Ha ez a doboz tartalmazza a számát, a fogolynak sikerült.
Ellenkező esetben a dobozban egy másik rab száma van, és ő ezzel a számmal nyitja ki a dobozt.
A fogoly addig ismétli a 2. és 3. lépést, amíg meg nem találja a számát, vagy ki nem nyit 50 fiókot.

A saját számától kiindulva és a hurkon keresztül a fogoly garantálja, hogy az ő számával végződő dobozok sorozatában van. Cselekedeteinek sikere csak attól függ, hogy ez a sorozat hosszabb-e 50 doboznál.

A probléma módosított változatában, ahol még egy karaktert adnak hozzá - egy ügyvédet, aki kinyithatja az összes dobozt, és ha szükséges, kettőt kicserélhet, a foglyok túlélése függetlenné válik a kezdeti permutációtól: erre az ügyvéd, miután felfedezett egy 50 doboznál hosszabb ciklust, megszakítja azt két, legfeljebb 50 hosszú ciklusra.

Példák

A stratégia sikerének okát a következő példa szemlélteti - 8 fogoly és doboz van, minden rab 4 dobozt tud kinyitni. Tegyük fel, hogy a börtön vezetője a következőképpen rendelte hozzá a foglyok számát a dobozokhoz:

dobozszámok	egy	2	3	négy	5	6	7	nyolc
fogolyszámok	7	négy	6	nyolc	egy	3	5	2

A fenti stratégia szerint a foglyok a következőképpen járnak el:

Az 1. fogoly először kinyitja az 1-es fiókot és megtalálja a 7-es számot. Ezután kinyitja a 7-es fiókot, és megtalálja az 5-öst. Ezután kinyitja az 5-ös fiókot, ahol megtalálja a számát, és így sikerül.
A 2. fogoly sorrendben kinyitja a 2-es, 4-es és 8-as dobozt, az utolsó dobozban megtalálja a számát.
A 3. fogoly kinyitja a 3. és 6. fiókot; az utóbbiban megtalálja a számát.
A 4. fogoly kinyitja a 4-es, 8-as és 2-es fiókot, mielőtt megtalálná a számát. Figyeld meg, hogy ez ugyanaz a ciklus, mint amivel a Prisoner 2 találkozott, bár egyik fogoly sem tud róla.
Az 5 és 8 közötti foglyok is hasonló módon találják meg a számukat.

Ebben a példában minden rab megtalálja a számát, de ez nem mindig van így. Például, ha megváltoztatja az 5. és 8. rovat tartalmát, akkor az 1. fogoly minden próbálkozását felhasználja az 1., 7., 5. és 2. dobozok kinyitásával, és nem találja a számát:

dobozszámok	egy	2	3	négy	5	6	7	nyolc
fogolyszámok	7	négy	6	nyolc	2	3	5	egy

És a következő elrendezésben az 1. fogoly kinyitja az 1-es, 3-as, 7-es és 4-es dobozt, és szintén nem fog sikerülni:

dobozszámok	egy	2	3	négy	5	6	7	nyolc
fogolyszámok	3	egy	7	5	nyolc	6	négy	2

Valójában ebben a példában 6 rab kivételével mindenki nem fogja megtalálni a számával ellátott dobozt.

Magyarázat a permutációk szempontjából

A foglyok számának dobozokban való elrendezése matematikailag leírható a számok 1-től 100-ig tartó permutációjaként. Egy ilyen permutáció az 1 -től 100-ig terjedő természetes számok halmazának egy az egyhez leképezése önmagára. Az olyan számsorozatot, amelyben az első a másodikhoz, a második a harmadikhoz, és így tovább, az utolsó pedig az elsőhöz megy, permutációs ciklusnak nevezzük. Minden permutáció felbontható diszjunkt ciklusokra, azaz olyan ciklusokra, amelyeknek nincs közös eleme. A fenti első példa permutációja hurokjelöléssel írható fel:

{\megjelenítési stílus (1~7~5)(2~4~8)(3~6)}

így két 3-as és egy 2-es ciklusból áll. A második példából származó permutáció rendre:

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

és egy 7 és egy 1 hosszúságú ciklusból áll.

A ciklikus jelölés nem egyedi, mivel egy hosszúsági ciklust az első szám kiválasztásától függően többféleképpen is fel lehet írni . A dobozokat a fent javasolt stratégia szerint kinyitva minden fogoly egy ciklust követ, amely a saját számával végződik. Nyolc fogoly esetében ez a stratégia akkor és csak akkor sikerül, ha a leghosszabb permutációs ciklus hossza legfeljebb 4. Ha a permutáció 5 vagy annál hosszabb ciklust tartalmaz, akkor az összes olyan fogoly, akinek a száma ebben a ciklusban van, nem éri el számuk négy lépés után. $l$ $l$

A siker valószínűsége

Az eredeti feladatban 100 fogoly lesz sikeres, ha a permutáció leghosszabb ciklusa legfeljebb 50. Ezért a túlélésük valószínűsége megegyezik annak valószínűségével, hogy egy 1-től 100-ig terjedő számok véletlenszerű permutációja nem tartalmaz hosszabb ciklust. mint 50. Ezt a valószínűséget a következőképpen határozzuk meg.

A számok 1 és 100 közötti permutációja legfeljebb egy hosszúságú ciklust tartalmazhat . Vannak módok számok kiválasztására egy ilyen ciklushoz, ahol a zárójelek kombinációkat jelölnek . Ezeket a számokat többféleképpen elrendezhetjük a ciklus köré , mivel a ciklikus szimmetria miatt van lehetőség azonos hosszúságú ciklus felírására . A fennmaradó számok különböző módon rendezhetők . Összességében a számok permutációinak száma 1-től 100-ig egy hosszúságú ciklussal $l>50$ ${\tbinom {100}{l))$ $(l-1)!$ $l$ $l$ $(100 liter)!$ $l>50$

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

Annak a valószínűsége , hogy egy ( egyenletes eloszlású ) véletlen permutáció nem tartalmaz 50 - nél hosszabb ciklust , a következőképpen számítjuk ki

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})\körülbelül 0,31183

hol a -edik harmonikus szám . Ezért a cikluskövetés stratégiáját alkalmazva a rabok az esetek mintegy 31%-ában túlélik [3] . Meglepő módon ez több mint 25% - csak két fogoly sikerének valószínűsége, akik véletlenszerűen és függetlenül választanak dobozokat. $H_n$ $n$

Aszimptotika

Ha 100 fogoly helyett a foglyokat vesszük figyelembe , ahol egy tetszőleges természetes szám, akkor a cikluskövetési stratégiát alkalmazva a fogvatartottak túlélési valószínűségét a következőképpen határozzuk meg. $2n$ $n$

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

Legyen az Euler-Mascheroni állandó . Akkor megkapjuk $\gamma$ $n\to\infty$

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

és ezért a túlélés valószínűsége hajlamos arra

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

Mivel a valószínűségek sorrendje monoton csökken , a cikluskövetés stratégiáját alkalmazva a rabok az esetek több mint 30%-ában életben maradnak, függetlenül a fogvatartottak számától [3] .

Optimalitás

2006-ban Eugene Curtin és Max Warsawer bebizonyította a cikluskövető stratégia optimálisságát. A bizonyítás egy hasonló problémával való egyenértékűségen alapul, amelyben minden fogoly tartózkodhat egy szobában és nézheti a dobozok kinyitását. Matematikailag ez az ekvivalencia a Foata-féle átmeneti lemmán alapul , amely a (kanonikus) ciklikus jelölés és a szabványos permutációs jelölés közötti egy az egyhez való megfelelés.[ adja meg ] . Az új problémában a túlélés valószínűsége nem függ a választott stratégiától, és megegyezik az eredeti probléma túlélési valószínűségével, ha a cikluskövetés stratégiáját alkalmazzuk. Mivel az eredeti feladat tetszőleges stratégiája is alkalmazható az új feladatra, de nem érhet el nagyobb túlélési valószínűséget, a kerékpározási stratégiának optimálisnak kell lennie [2] .

Történelem

A 100 fogoly és 100 doboz problémával először 2003-ban Peter Miltersen dán informatikus foglalkozott, aki Anna Gal-lal együtt publikálta a 30. Nemzetközi Automaták, Nyelvek és Programozás Kollokvium (ICALP) eredményeiről szóló . ). Az ő változatukban az A játékos (a börtön vezetője) véletlenszerűen papírcsíkokat fest a B-csapat játékosainak (foglyok) nevével pirosra vagy kékre, és minden csíkot külön dobozba helyez, bár néhány doboz üres lehet. . Ahhoz, hogy a B csapat nyerjen, minden tagjának helyesen meg kell neveznie színét a dobozok felének kinyitása után [4] .

Kezdetben Milterson azt feltételezte, hogy a győzelem valószínűsége a játékosok számának növekedésével gyorsan nullára csökken. Sven Skyum, az Aarhusi Egyetem Miltersen munkatársa azonban kerékpáros stratégiát dolgozott ki egy olyan problémára, amelyben nincsenek üres dobozok. Ennek eredményeként a cikkben ennek a stratégiának a megtalálása gyakorlatnak maradt. A cikket díjazták[ pontosítás ] a legjobb publikáció díjai [2] .

2004 tavaszán ez a probléma Joe Buhler és Alvin Berlekamp rejtvényrovatában jelent meg a The Mathematical Research Institute negyedévente [5] . A következő években ezt a problémát a matematikai irodalomban különféle megfogalmazásokban kezdték használni - például kártyákkal az asztalon [6] vagy pénztárcákkal a szekrényekben [2] .

A 100 fogoly és 100 doboz probléma formájában 2006-ban Christoph Peppe állította fel a Spektrum der Wissenschaft (a Scientific American német változata ) [7] és Peter Winkler a College Mathematics Journal -ban [8]. . Kisebb módosításokkal ezt a változatot Philippe Flajolet és Robert Sedgwick [1] , valamint Richard Stanley [3] kombinatorika tankönyveiben alkalmazta .

Lásd még

A három rab feladata

Jegyzetek

↑ 1 2 Philippe Flajolet, Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press, p. 124
↑ 1 2 3 4 Eugene Curtin, Max Warshauer (2006), A szekrényrejtvény , Mathematical Intelligencer Vol . 28: 28–31 , DOI 10.1007/BF02986999
↑ 1 2 3 4 Richard P. Stanley (2013), Algebraic Combinatorics: Walks, Trees, Tableaux and More , Springer, p. 187–189
↑ Gál Anna, Peter Bro Miltersen (2003), The cell probe complexity of succinct data structures, Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP) , p. 332–344
↑ Joe Buhler, Elwyn Berlekamp (2004), Rejtvények oszlopa , p. 3
↑ Richard E. Blahut (2014), Cryptography and Secure Communication , Cambridge University Press, p. 29–30
↑
↑ Peter Winkler (2006), Names in Boxes Puzzle , p. 260,285,289

Irodalom

Philippe Flajolet , Robert Sedgewick (2009), Analytic Combinatorics , Cambridge University Press
Richard P. Stanley (2013), Algebrai kombinatorika: séták, fák, táblák és még sok más , Springer
Peter Winkler (2007), Mathematical Mind-Benders , Taylor és Francis