Feladat: N.59 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Dombi Gergely ,  Gyarmati Katalin ,  Izsák Ferenc ,  Makai Márton ,  Méder Áron ,  Perényi Márton ,  Póczos Barnabás ,  Szádeczky-Kardoss Szabolcs ,  Valkó Benedek 
Füzet: 1995/december, 539 - 540. oldal  PDF file
Témakör(ök): Klasszikus valószínűség, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/február: N.59

Egy áramköri lapon a P, Q, R, S chip-eket minden lehetséges módon vezeték köti össze. Gazdaságossági okokból a QS vezeték alul halad, a többiek felül. Egy elektron bolyongásra indul a P-ből oly módon, hogy útja során minden chip-nél egyenlő valószínűséggel választ a lehetséges 3 irány közül. Mekkora a valószínűsége annak, hogy az elektron először csak az 1995. lépésben kerül az áramköri lap alsó oldalára?

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.

Az elektron pontosan akkor kerül először csak az 1995-ik lépésben az áramköri lap alsó oldalára, ha az első 1994 lépéssel a Q vagy az S chip-be jut el anélkül, hogy a QS vezetéken áthaladna, majd az 1995-ik lépésben teszi meg a QS utat. Ha tehát rendre pi, qi, ri, si jelöli annak a valószínűségét, hogy az elektron az első i lépésben a QS út elkerülésével a P, Q, R, S chip-be jut el, akkor a feladatban keresett valószínűséget (q1994+s1994)/3 adja meg. Nyilván

p0=1,q0=0,r0=0,s0=0,
továbbá a feltételes valószínűség tétele szerint
pi+1=qi+ri+si3,qi+1=pi+ri3,ri+1=pi+qi+si3,si+1=pi+ri3.
Célszerű bevezetni az ai=pi+ri, bi=qi+si jelöléseket, ezekkel ugyanis a keresett valószínűség b1994/3, továbbá a fentiekből
a0=1ésb0=0,illetveai+1=ai+2bi3ésbi+1=2ai3.
Innen ai-re az ai+1=13ai+49ai-1 lineáris rekurzió adódik az a0=1 és a1=13 kezdőértékkel. Az ai-t keressük c1x1i+c2x2i alakban alkalmas c1 és c2 konstansokkal és az x2=13x+49 egyenlet x1,2 gyökeivel, hiszen minden ilyen alakú sorozat kielégíti a rekurzió egyenletét. A kezdőértékekből a konstansokra egy lineáris egyenletrendszer adódik, amely egyértelműen megoldható; végeredményben azt kapjuk, hogy
ai=317[(1+176)i+1-(1-176)i+1].
Így a feladatban kérdezett valószínűség
P=b19943=2a19939=2317[(1+176)1994-(1-176)1994]=2,42...10-138.

 Makai Márton (Debrecen, Fazekas M. Gimn., III. o.t.) dolgozata alapján