Feladat: Gy.2409 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Apáti Mónika ,  Aranyi F. ,  Balogh 171 J. ,  Beke T. ,  Benczúr P. ,  Benkő D. ,  Binder Zsuzsanna ,  Csanádi P. ,  Csirik J. ,  Fejérdy Zsófia ,  Figeczky G. ,  Györki M. ,  Hahn Zsuzsa ,  Hajnal Z. ,  Imreh Cs. ,  Jalsovszky P. ,  Károlyi A. ,  Keleti T. ,  Kondacs A. ,  Kozma K. ,  Kullman T. ,  Lois L. ,  Mikusi Cs. ,  Novák Vera ,  Pór A. ,  Siklér F. ,  Sustik M. ,  Temesvári Anikó ,  Toronyi L. ,  Weisz Cs. ,  Zerkovitz Zsuzsanna 
Füzet: 1988/január, 16 - 18. oldal  PDF  |  MathML 
Témakör(ök): Permutációk, Klasszikus valószínűség, Gyakorlat
Hivatkozás(ok):Feladatok: 1987/április: Gy.2409

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. Számozzuk meg a perselyeket, illetve a hozzájuk illő kulcsokat 1-től 30-ig, ezután helyezzük el a kulcsokat a zárt perselyekben, majd állítsuk sorba a perselyeket. A feltétel szerint ekkor a 30 kulcsnak 30!-féle egyenlően valószínű sorrendje lehetséges. Minden egyes sorrendnek a kulcsok egy részének a kihúzási sorrendje felel meg, nekünk azoknak a sorrendeknek a számára van szükségünk, amikor valamennyi perselyt fel tudjuk nyitni, tehát az összes kulcsot kihúztuk.
Egy adott elhelyezés esetén pontosan akkor akadunk el, ha már nyitva van az a persely, amelynek a kulcsa éppen a kezünkbe került. Maga a kulcs ekkor csak az 1-es számú, feltört persely kulcsa lehet, hiszen erőszakoskodás nélkül felnyitott persely kulcsa nem lehet későbbi perselyben. Amennyiben tehát valamennyi perselyt fel tudjuk nyitni, akkor harmincadiknak az 1-es számú, feltört persely kulcsát húzzuk ki. Hívjuk a kulcsok ilyen sorrendjeit a perselyekben jó sorrendnek.
Mármost a kulcsok minden lehetséges S=(s1,s2,...,s30) kihúzási sorrendjének ‐ ahol tehát s30=1 ‐ megfeleltethető a kulcsoknak egy olyan S*=(s1*,s2*,...,s30*) jó sorrendje a perselyekben, melynek során éppen az S sorrendben férünk hozzá a kulcsokhoz. Nyilván

s1*=s1,ss1*=s2,ss2*=s3,...,ss28*=s29ss29*=s30=1.

Az S↔S* megfeleltetés jól láthatóan kölcsönösen egyértelműen képezi le az 1-gyel végződő permutációk halmazát a jó sorrendek halmazára, így éppen annyi jó sorrend van, mint ahányféleképpen sorba rakhatjuk a 30 darab kulcsot úgy, hogy az 1-es számú álljon az utolsó helyen. Mivel pedig az ilyen sorrendek száma éppen 29!, a keresett valószínűség 29!30!=130.
A második esetben, amikor kezdetben két perselyt törünk föl ‐ föltehető, hogy ezek az 1-es és a 2-es sorszámúak ‐ éppen azok a kihúzási sorrendek valósíthatók meg, amikor az 1-es, vagy pedig a 2-es számú kulcsot húzzuk ki utoljára, harmincadiknak.
Az előzőekhez hasonlóan az ilyen sorrendeknek most is kölcsönösen egyértelműen felel meg egy és csak egy megfelelő elhelyezése a kulcsoknak, így ez utóbbiak száma most 2⋅29!. Két feltört persely esetén tehát 2⋅29!30!=230 érték adódik a keresett valószínűségre.
 

II. megoldás. Belátjuk, hogy ha n persely közül k darabot törünk föl kezdetben (1≦k≦n), akkor kn annak a valószínűsége, hogy ezután már valamennyi perselyt fel tudjuk nyitni.
Jelölje ennek az eseménynek a valószínűségét pn,k.
Nyilvánvaló, hogy pk,k=1. Legyen most n>k és tekintsük az n-edik perselyt. Ha ez a saját kulcsát tartalmazza ‐ ennek 1/n a valószínűsége ‐ akkor ehhez a perselyhez nem tudunk hozzáférni. Ha az n-edik persely az i-edik kulcsot tartalmazza, az n-edik persely kulcsa pedig a j-edik perselyben van (1<i, j<n), akkor ez az elrendezés pontosan akkor nyitható fel, ha ez igaz arra az n-1 perselyre is, ahol az i-edik kulcsa a j-edik perselyben van. Mivel ennek pn-1,k a valószínűsége, így
pn,k=(1-1n)pn-1,k=(1-1n)(1-1n-1)...(1-1k+1)pk,k==n-1n⋅n-2n-1⋅...⋅kk+1=kn


valóban.