Feladat: B.4491 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Williams Kada 
Füzet: 2014/március, 147 - 148. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Logikai feladatok, Kombinatorikai leszámolási problémák, Permutációk
Hivatkozás(ok):Feladatok: 2012/november: B.4491

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Feltehető, hogy a fiókok 1-től 100-ig vannak megszámozva. Legyen a stratégia a következő: első lépésként a rabok számozzák meg magukat 1-től 100-ig, és minden rab jegyezze meg, hogy kinek mi a száma. Ezután az elsőként hívott rab nyissa ki a sorszámának megfelelő fiókot. Ha ebben a saját nevét találja, akkor elvezetik, ha nem, akkor annyiadik fiókot nyissa ki, amennyi az ebben szereplő rab sorszáma. Ha itt már a saját nevét találja, akkor elvezetik, ha nem, akkor ismét annyiadik fiókot nyissa ki, amennyi az itt szereplő rab sorszáma, és így tovább ... Folytassa e szerint a módszer szerint, amíg meg nem találja a saját nevét, vagy amíg 50 fiókot ki nem húz (sikertelenül). Majd az összes többi rab is így nyissa ki a fiókokat, mindenki a saját sorszámával megegyező fiókban kezdve a keresést.
Megmutatjuk, hogy ezzel a stratégiával a raboknak 30%-nál nagyobb esélyük van a szabadulásra. Azt mondjuk, hogy az i1-edik, i2-edik, ..., ik-adik rabok egy kört alkotnak, ha az i1-edik fiókban az i2-es számú rab neve szerepel, i2-edik fiókban az i3-asé, ..., az ik-1-edikben az ik-asé, végül az ik-adik fiókban i1-esé. Csak akkor lesz olyan rab, aki nem szabadul ki (ez egyenértékű azzal, hogy mindenkit kivégeznek), ha létezik 50-nél több rabból álló kör. Mivel a körök diszjunktak, ezért ilyen csak egy lehet. Annak a valószínűsége, hogy van k (ahol k51) hosszú kör

(100k)(k-1)!(100-k)!100!=1k,
mert a kört alkotó k rabot (100k)-féleképpen választhatjuk ki, az ő sorrendjük (k-1)! féle lehet, a többi rabé pedig (100-k)! féle. Így a rabok szabadulásának valószínűsége
1-(151+152+...+1100)0,3118,
ami több, mint 30%.