Ész Ventura: Íme a zsebtolvajos feladvány megoldása

Támogasd a tudomány népszerűsítését, segítsd a munkánkat!

102. feladványunkban borsóleves-ködben zsebtolvaj garázdálkodott a Regent’s Parkban. A feladat szerint két kijárattal rendelkező parkban 98 sétáló volt, ezen kívül 2 rendőr és a zsebtolvaj, akik mind össze-vissza bolyongtak úgy, hogy bármely két embernek, vagy bármely embernek és valamely kapunak a találkozása azonos valószínűségű volt adott idő alatt. Az volt a feltételezés a tolvajról, hogy ha olyan sétálóval találkozik, akivel még nem találkozott, akkor kirabolja, ha rendőrrel fut össze, akkor vége a garázdálkodásnak, ha viszont megtalálja a kijáratot, akkor távozik az addig rabolt pénzzel és értékekkel. A sétáló emberek és a rendőrök eközben nem mennek ki a parkból. A kérdés az volt, hogy a tolvaj mekkora valószínűséggel menekül el, és ha elmenekül, akkor átlagosan hány ember kirablása után.

Az első kérdésre könnyű a válasz, hiszen a tolvaj tevékenysége két módon érhet véget: vagy egy rendőrnél, vagy egy kapunál. Csakhogy rendőrből is és kapuból is kettő van, és ezekkel a találkozás valószínűsége a feladat szerint minden időpillanatban egyforma, tehát az elmenekülés esélye pont 50% lesz. Jól okoskodtunk? Nem teljesen, elvileg ugyanis van még egy lehetőség, nevezetesen az, hogy a tolvaj soha nem találkozik se rendőrrel, se valamelyik kapuval, hanem végtelen sokáig bolyong, és csak sétálókkal találkozik. Könnyen belátható azonban, hogy ennek nulla a valószínűsége, ezért tényleg a 100%-ot kell két részre osztanunk, és így lesz teljes a gondolatmenet.

Nézzük most a második kérdést, amit Déva Gergely olvasónk gondolatmenete alapján tárgyalunk. Tegyük fel, hogy tolvajunk már N embert kirabolt. Ezután három dolog történhet vele: nem rabol ki több embert, és végül elkapják (1), nem rabol ki több embert, és végül elmenekül (2), kirabol legalább még egy embert (3). Annak, hogy ezek közül egyik se történjen meg, azaz ezentúl mindig csak kiraboltakkal találkozzon végtelen sokáig, nulla a valószínűsége. Nézzük ezen három eset valószínűségeit rendre N függvényében, és nevezzük őket p1(N), p2(N) és p3(N)-nek.

Annak a valószínűsége, hogy a következő találkozás alkalmával elkapják a tolvajt, 2/102, mert két rendőr van, és 102 entitással találkozhat a tolvaj összesen, a feladat szerint mindegyikkel azonos valószínűséggel. Annak a valószínűsége, hogy a második találkozásnál kapják el, és addig nem rabol tovább, (N/102)·(2/102), hiszen az első találkozásnál az eddig kirabolt N ember egyikével kell találkoznia, majd a két rendőr valamelyikével. Hasonló módon annak a valószínűsége, hogy a harmadik találkozásnál kapják el, és addig nem rabol, (N/102)·(N/102)·(2/102), és így tovább. Ezek a valószínűségek tehát egy mértani sorozatot alkotnak, és ezeket kell összegeznünk, ha annak a teljes valószínűségére vagyunk kíváncsiak, hogy a tolvaj nem rabol ki több embert, és végül elkapják, de nem érdekel minket, hogy hányadik lépésben. Ennek a mértani sorozatnak az összege p1(N) = (2/102)/(1 - N/102) = 2/(102-N).

Mármost annak a valószínűsége, hogy már nem rabol ki több embert, és megszökik ugyanannyi, mint annak, hogy nem rabol ki több embert, és elkapják, mert két rendőr és két kapu van, tehát a rendőrrel vagy a kapuval találkozás esélye, vagyis az elfogás és szökés esélye azonos, éppúgy, mint a legelején. Tehát p2(N) = p1(N). Végezetül annak a valószínűsége, hogy kirabol legalább még egy embert, az épp a maradék lesz, mert nincs más lehetőség, ahogy azt már megbeszéltük. Tehát p3(N) = 1 - p1(N) - p2(N) = 1 - 2·p1(N) = (98-N)/(102-N).

Ezek után a fentiek felhasználásával annak a Q(N) valószínűsége, hogy a tolvaj pontosan N embert rabol ki, majd megszökik, az alábbiakból tevődik össze. Kezdetben 0 embert rabol ki, és ki kell rabolnia az elsőt, ennek valószínűsége (98-0)/(102-0), majd a másodikat is ki kell rabolnia, ennek a valószínűsége (98-1)/(102-1), és így tovább. Végül eljutunk oda, hogy már (N-1)-et kirabolt, de még egyet, azaz az N-ediket is ki kell rabolnia, aminek (98-(N-1))/(102-(N-1)) lesz a valószínűsége. Legvégül pedig már nem rabolhat többet, és el kell menekülnie, ennek a valószínűsége 2/(102-N). Ezek egymás után bekövetkező események, azaz a valószínűségeket mind össze kell szoroznunk, hogy megkapjuk a keresett teljes valószínűséget, amire némi egyszerűsítés után az alábbi adódik: Q(N) = 2·(99-N)·(100-N)·(101-N)/99/100/101/102.

A feladat viszont a várható értékre kíváncsi, azaz a Q(N) valószínűséggekel súlyozva kell átlagot képeznünk, vagyis minden lehetséges N-re összegezni kell a Q(N)·N szorzatokat. N viszont maximum 98 lehet, ahány sétáló van a parkban, ez tehát már egy véges összeg lesz, amit könnyen ki lehet számítani, és a végeredmény 49/5 = 9,8. Tehát abban az esetben, ha nem kapják el a rendőrök a tolvajt, átlagosan majdnem 10 ember végigrablása után jut ki a parkból.

Kapcsolódó cikk a Qubiten: