Feladat: 1971. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bajmóczy Ervin ,  Berényi Péter ,  Füredi Zoltán ,  Komjáth Péter ,  Máté András ,  Móri Tamás ,  Ruzsa Imre 
Füzet: 1972/február, 56 - 58. oldal  PDF  |  MathML 
Témakör(ök): Klasszikus valószínűség, Kombinatorikai leszámolási problémák, Számsorozatok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1972/február: 1971. évi Kürschák matematikaverseny 3. feladata

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.

I. megoldás. Mielőtt a felnyitáshoz kezdenénk, rakjuk sorba a perselyeket azzal a kettővel kezdve, amelyeket majd feltörünk és írjuk rájuk a sorszámukat.
Miután találomra dobták be a kulcsokat a perselyekbe, és a feltörni szánt két perselyt is csak találomra tudjuk kiválasztani, így egyenlő eséllyel jöhet létre a kulcsok minden elrendezése a perselyekben.
Most feltörjük az első két perselyt. Ha az első perselyben nem a saját kulcsa volt, akkor a benne található kulccsal kinyitjuk azt a perselyt, amelyiket nyitja, kivesszük a benne található kulcsot és a perselyt félreállítjuk. Az újabb kulccsal kinyitjuk a megfelelő perselyt, kivesszük belőle a kulcsot és a perselyt az előbbi mellé állítjuk, és így haladunk tovább, amíg lehet.
Ha közben előkerül a második persely kulcsa is, úgy járunk el, mintha azt fel sem törtük volna, kivesszük abból is a kulcsot és a perselyt a nyitott perselyek sorába állítjuk.
Akkor akadunk meg, amikor az első persely kulcsa kerül elő és ez lehet mindjárt akkor is, amikor az első perselyből vesszük ki a benne levő kulcsot. Világos, hogy más nyitott persely kulcsa nem kerülhet elő, mert az már korábban előkerült, és egy perselynek csak egy kulcsa van.
Amikor az első persely kulcsa kerül elő, akkor az első perselyt is áttesszük a felnyitott perselyek sorába. Ezután kivesszük a második perselyben levő kulcsot, ha még nem került elő, és folytatjuk az eljárást. Ez befejeződik, ha a második persely kulcsa is előkerült.
Ha még nem nyitottunk ki közben minden perselyt, ez a kérdezett valószínűség szempontjából kedvezőtlen eset. Ekkor is folytassuk az eljárást úgy, hogy valahányszor elakadunk, mindig feltörjük az első még ki nem nyitott perselyt.
Ilyen módon minden kulcselosztáshoz a perselyekben hozzárendeltük a (nyitott) perselyeknek egy sorrendjét. Fordítva, a perselyelrendezést ismerve mindegyikbe vissza tudjuk tenni azt a kulcsot, amelyik abba volt bedobva. Az első helyen álló persely kulcsát kell az 1-es sorszámú perselybe tenni, ezután az első sorszámú perselyig mindegyiknek a kulcsát az előtte álló perselybe. Az 1-es sorszámú persely után álló persely kulcsa a legkisebb sorszámú még üres perselybe kerül, az addig álló perselyek kulcsa az előttük levő perselybe és így tovább.
A perselyek elrendezése akkor tartozik a kulcsok egy kedvező sorrendjéhez, ha az utolsó helyen az 1-es vagy 2-es sorszámú persely áll, különben kedvezőtlen kulcs-sorrendhez tartozik. Bármelyik persely áll is az utolsó helyen, az előtte állókat mindig ugyanannyiféleképpen lehet elrendezni, így az, hogy az utolsó helyen egy-egy megadott persely áll, csupa egyenlő valószínűségű esemény, összesen 30. Ezek közül 2 kedvező, tehát a keresett valószínűség 1/15.
Világos, hogy általában, ha n persely van és közülük k-t törünk fel (k≤n), akkor k/n a valószínűsége annak, hogy mindegyik perselyt ki tudjuk nyitni.

 
Megjegyzés. A versenyzők nagy része összeszámolta az összes és a kedvező kulcselosztásokat, részben úgy, hogy a feltörésre szánt perselyek kiválasztását is az eseményekhez számította. A kedvező események összeszámolását többen azzal könnyítették meg, hogy minden olyan elrendezéshez, amelyben lényeges volt a második persely feltörése is, hozzápárosítottak kölcsönösen egyértelműen egy olyant, amelyben a második persely feltörése nélkül is már mind kinyitható. Ilyent kapunk, ha az első persely kulcsát tesszük abba a perselybe, amelyikben a másodiké volt és viszont.
 
II. megoldás. Azt fogjuk bizonyítani, hogy ha n perselybe dobjuk be kulcsaikat találomra és kettőt feltörünk közülük, akkor 2/n annak a valószínűsége, hogy minden perselyt ki tudjunk nyitni.
Jelöljük a keresett valószínűséget pn-nel. Természetesen p2=1. Megmutatjuk, hogy ha n≥2, akkor
pn+1=nn+1pn.(1)
Ebből már következik, hogy
pn=n-1n⋅n-2n-1⋅...⋅23⋅p2=2n,
és a feladat esetére p30=1/15.
Tekintsük az n+1 kulcsnak egy E elhelyezését a perselyekben. Jelölje r annak a perselynek a sorszámát, amelyikben az (n+1)-edik persely kulcsa van és s azét, amelyiknek a kulcsa az (n+1)-edikben van. Világos, hogy vagy r is és s is (n+1)-gyel egyenlő (az utolsó persely a saját kulcsát tartalmazza), vagy mindkettő kisebb, mint n+1.
Az előbbi esetben az n+1-edik perselyt figyelmen kívül hagyva kapjuk az első n persely kulcsainak egy E1 elhelyezését az első n perselyben. Az utóbbiban is hozzárendelünk E-hez egy ilyen E1 elrendezést, azt, amelyik annyiban különbözik csak E-től, hogy az r-edik perselybe az s-edik kulcsát dobjuk.
Ilyen módon minden E-hez rendeltünk egy E1-et. Megfordítva, ha E1-et ismerjük, ez keletkezhetett E-ből úgy, hogy az első, vagy a második, vagy ..., vagy az n-edik perselyből vettük ki az (n+1)-edik persely kulcsát és cseréltük ki az (n+1)-edikben levő kulccsal vagy úgy, hogy figyelmen kívül hagytuk az (n+1)-edik perselyt, amelyikben a saját kulcsa volt. Így az n kulcs egy E1, elhelyezése az n+1 kulcs (n+1)-féle különböző elhelyezéséhez van hozzárendelve.
Ha most az első 2 perselyt feltörjük, akkor E-ben és E1-ben ugyanazokat a perselyeket tudjuk kinyitni, amíg csak el nem jutunk az r-edikhez. Ha ez bekövetkezik, akkor E-ben felnyithatóvá válik az (n+1)-edik persely, majd azt felnyitva az s-edik, E1-ben pedig közvetlenül az s-edik. Tovább ismét mind a két kulcselhelyezés esetén ugyanazok a perselyek nyithatók ki.
Akkor és csak akkor nyitható tehát fel az E kulcselhelyezés esetén mind az n+1 persely, ha a hozzárendelt E1 kulcselhelyezéssel az első n persely felnyitható és az (n+1)-edik perselyben nem a saját kulcsa van.
Ezek szerint az n kulcs minden lehetséges elhelyezéséhez az n+1 kulcs n+1 elhelyezése tartozik és minden olyan elhelyezéshez, amiben az összes persely felnyitható, az n+1 persely kulcsainak n ilyen elhelyezése. Ez éppen az (1) összefüggést szolgáltatja.
 
Megjegyzés. Ugyanígy látható, hogy akkor is fennáll (1), ha pn annak a valószínűsége, hogy k persely feltörése esetén minden persely kinyithatóvá válik. Mivel ekkor pk=1, így ismét adódik, hogy ebben az általánosabb esetben pn=k/n.