Feladat: F.3042 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Becker Johanna ,  Bodon Ferenc ,  Braun Gábor ,  Dombi Gergely ,  Elek Péter ,  Erdélyi László ,  Farkas Illés ,  Farkas Péter ,  Frenkel Péter ,  Gémes Tamás ,  Gröller Ákos ,  Hegedűs Viktor ,  Hegyi Barnabás ,  Katona János ,  Kerekes Tamás ,  Lovász Zoltán ,  Majlender Péter ,  Makai Márton ,  Németh Zoltán ,  Orbán András ,  Pap Gyula ,  Pápai Mihály ,  Peltz Csaba ,  Perényi Márton ,  Puskás Zsolt ,  Ruzsa Gábor ,  Sánta Zsuzsa ,  Somogyi Balázs ,  Terpai Tamás ,  Tóth Gábor Zsolt ,  Ugron Balázs ,  Valkó Benedek ,  Véber Miklós ,  Vörös Zoltán 
Füzet: 1995/május, 285 - 290. oldal  PDF file
Témakör(ök): Sorozat határértéke, Polinomok szorzattá alakítása, Számsorozatok, Klasszikus valószínűség, Rekurzív sorozatok, Feladat
Hivatkozás(ok):Feladatok: 1994/december: F.3042

Egy a Ki nevet a végén?-hez hasonló játékban egy bábuval legalább 100 lépést kell megtenni. Egyszerre véletlenszerűen 1, 2, 3 vagy 4 mezővel léphetünk tovább. Jelölje pn annak a valószínűségét, hogy rálépünk az n-edik mezőre. (A bábu a nulladik mezőről indul.) Bizonyítsuk be, hogy 0,399999<p100<0,400001.

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.

A megoldás során felhasználjuk a ,,Játék mindenkinek'' rovatunkhoz fűzött megjegyzésekben olvashatókat. (KöMaL 1994/8‐9. sz., 430‐432. o.)
Terjesszük ki pn definícióját n=0,-1,-2,-3-ra a következőképpen:

p-1=p-2=p-3=0,p0=1.(1)
(Ezeknek teljesen szemléletes jelentése van.) Világos, hogy az n-edik mezőre az (n-1)-edik, (n-2)-edik, (n-3)-adik és (n-4)-edik mezőről léphetünk, a megfelelő utolsó dobás valószínűsége 14, ezért a teljes valószínűség tétele alapján
pn=14pn-1+14pn-2+14pn-3+14pn-4(n=1,2,...),
vagyis
pn-14pn-1-14pn-2-14pn-3-14pn-4=0.(2)
E sorozat karakterisztikus polinomja:
p(x)=x4-14x3-14x2-14x-14.

Legyenek a p(x)=0 egyenlet gyökei, ideértve a komplexeket is, z1, z2, ..., zk, multiplicitásuk rendre α1, α2, ..., αk, azaz p(x) gyöktényezős alakja
p(x)=(x-z1)α1(x-z2)α2...(x-zk)αk.
Ismeretes, hogy a (pn) sorozat n-edik eleme
pn=a1(n)z1n+a2(n)z2n+...+ak(n)zkn(3)
alakú, ahol ai(x) (i=1, 2, ..., k) valamilyen αi-nél alacsonyabb fokú polinom; és megfordítva, ha a sorozat ilyen alakú, akkor igaz rá a rekurzió.
A p(x) polinom egyik gyöke az 1, és ez csak egyszeres gyök, mert
p(x)=(x-1)(x3+34x2+12x+14),(4)
és a második tényezőnek az 1 nem gyöke. A többi gyök abszolút értékben 1-nél kisebb, mert |x|1 esetén |p(x)||x|4-|x|30, és egyenlőség csak akkor van, ha x=1. Így a1 konstans polinom, és a (3) többi tagja zérushoz tart, ha n tart a végtelenhez.
Most meghatározzuk a1-et, ami az előbbiek alapján a pn sorozat határértéke. Definiáljuk a qn sorozatot a következőképpen:
qn=a2(n)z2n+...+ak(n)zkn=pn-a1.(5)
A qn sorozatra (4) miatt fennáll, hogy
qn+34qn-1+12qn-2+14qn-3=0,
azaz
(pn-a1)+34(pn-1-a1)+12(pn-2-a1)+14(pn-3-a1)=0.
Behelyettesítve n=0-t,
(1-a1)+34(0-a1)+12(0-a1)+14(0-a1)=0,
amiből a1=25. Tehát
limpn=25.(6)

Megbecsüljük a konvergencia sebességét. Mivel
(x-23)(x3+34x2+12x+14)=x4+112x3-112x-16,
a qn sorozatra a
qn+112qn-1-112qn-3-16qn-4
rekurzió is teljesül. Ebből következik, hogy
|qn|112|qn-1|+112|qn-3|+16|qn-4|13max(|qn-1|,|qn-3|,|qn-4|).

Bebizonyítjuk, hogy |qn|(13)n/4. Ez n=-3, -2, -1, 0 esetén könnyen ellenőrizhető. Ha pedig igaz n<m esetén (m=1, 2, ...), akkor
|qm|13max(|qm-1|,|qm-3|,|qm-4|)13(13)m-44=(13)m4.

Ha n=100-at behelyettesítünk, akkor
|q100|=|p100-a1|=|p100-0,4|(13)25<10-6,
vagyis
0,399999<p100<0,400001.

Megjegyzések. 1. Ha d lapú dobókockával dobunk, azaz egyforma valószínűséggel lépünk 1, 2, ..., d-1 vagy d mezőt, akkor is megoldható a feladat. (d=6-ra a megoldás már megjelent a KöMaL 1994/8‐9. számának 430‐432. oldalán.)
Általánosításunk teljes egészében a fent ismertetett gondolatmenetet fogja követni.
Legyen pn annak valószínűsége, hogy rálépünk az n-edik mezőre és legyen p0=1, p-1=p-2=...=p-d=0.
Ekkor világos, hogy n=0,1,... esetén
pn=i=1d1dpn-i,
vagyis
pn-1dpn-1-1dpn-2-...-1dpn-d=0.
Most
p(x)=xd-1dxd-1-1dxd-2-...-1d.
Ennek egyik gyöke z1=1, a többi gyök abszolút értéke 1-nél kisebb. A z1=1 multiplicitása, α1=1, mert
p(x)=(x-1)(xd-1+d-1dxd-2+d-2dxd-3+...+1d),
és a második tényező x=1 esetén pozitív.
A qn=pn-a1 sorozatra teljesül, hogy
qn+d-1dqn-1+d-2dqn-2+...+1dqn-d=0,
azaz
(pn-a1)+d-1d(pn-1-a1)+d-2d(pn-2-a1)+...+1d(pn-d-a1)=0.
Behelyettesítve n=0-t,
(1-a1)+d-1d(0-a1)+d-2d(0-a1)+...+1d(0-a1)=0,
amiből
a1=11d+2d+...+dd=2d+1.
Tehát
limpn=2d+1.

A |qn| megbecsüléséhez:
(x-d-2d-1)(xd-1+d-1dxd-2+d-2dxd-3+...+1d)==xd+1d(d-1)xd-1-1d(d-1)xd-3-2d(d-1)xd-4-...-d-2d(d-1),
amiből qn-re
qn+1d(d-1)qn-1-1d(d-1)qn-3-2d(d-1)qn-4-...-d-2d(d-1)qn-d=0,
ahonnan
|qn|1+1+2+...+(d-2)d(d-1)max(|qn-1|,|qn-3|,...,|qn-d|)<<(1-2d-4d(d-1))max(|qn-1|,|qn-3|,...,|qn-d|).
Innen pedig
|pn-2d+1|=|qn|(1-2d-4d(d-1))nd.
Ez a becslés 0-hoz tart d3 esetén. (Ha d=1, akkor az állítás triviális. Ha d=2, akkor z2=-12 és |qn|=(12)n.)
 Farkas Péter (Budapest, Szent István Gimn., IV. o. t.)

 
2. A megoldásban felírt összefüggéseket a lineáris rekurzív sorozatok elméletére való hivatkozás nélkül is be lehet bizonyítani, többnyire teljes indukcióval.
Induljunk ki a (2) összefüggésből, ennek alapján bebizonyítjuk a
(pn-25)+34(pn-1-25)+12(pn-2-25)+14(pn-3-25)=0(7)
azonosságot. Ez n=0-ra, mint láttuk, igaz. Ha pedig igaz n=m-1-re, akkor
(pm-25)+34(pm-1-25)+12(pm-2-25)+14(pm-3-25)==(pm-25)+34(pm-1-25)+12(pm-2-25)+14(pm-3-25)--(pm-14pm-1-14pm-2-14pm-3-14pm-4)==(pm-1-25)+34(pm-2-25)+12(pm-3-25)+14(pm-4-25)=0.
Ezzel (7)-et igazoltuk. Írjuk fel (7)-et n-1-re is:
(pn-1-25)+34(pn-2-25)+12(pn-3-25)+14(pn-4-25)=0(8)
Vonjuk ki (7)-ből (8) 23-szorosát:
(pn-25)+34(pn-1-25)+12(pn-2-25)+14(pn-3-25)--23(pn-1-25)-12(pn-2-25)-13(pn-3-25)-16(pn-4-25)=(pn-25)+112(pn-1-25)-112(pn-3-25)-16(pn-4-25)=0.

Ezzel az összes szükséges azonosságot igazoltuk.
3. Tegyük fel, hogy a lehetséges lépéshosszok a h1<...<hd pozitív egészek, ezek valószínűsége q1,...,qd>0. Legyen pn továbbra is annak valószínűsége, hogy rálépünk az n-edik mezőre. Bebizonyítjuk, hogy ha a pn sorozat konvergens, akkor határértéke
limpn=1q1h1+q2h2+...+qdhd.
(Azt nem nehéz bebizonyítani, hogy pn akkor konvergens, ha a h1,...,hd számoknak nincs 1-nél nagyobb közös osztója.)
Definiáljuk az X0,X1,... véletlen mennyiségeket (valószínűségi változókat) a következőképpen:
Xn={0,ha az  n-edik mezőre nem lépünk rá;i,ha az  n-edik mezőre rálépünk és ott  i-t dobunk.

Ekkor X0+X1+...+Xm az első m mezőn tett lépések összege, vagyis az első olyan mező sorszáma, amely az m-edik után van és rálépünk. Ez biztosan m+1 és m+hd között van, tehát
m+1X0+X1+...+Xmm+hd.

Ebből következik, hogy az összeg várható értéke is e két határ között van:
m+1E(X0+X1+...+Xm)=E(X0)+E(X1)+...+E(Xm)m+hd.
(A várható értéket mindig lehet tagonként számolni.)
Mivel
E(Xn)=pnq1h1+pnq2h2+...+pnqdhd=pn(q1h1+...+qdhd),
ez azt jelenti, hogy
m+1(p0+p1+...+pm)(q1h1+...+qdhd)m+hd,
amit (m+1)(q1h1+...+qdhd)-vel osztva
1q1h1+...+qdhdp0+p1+...+pmm+1(1+hd-1m+1)1q1h1+...+qdhd.
Mivel m esetén
(1+hd-1m+1)1,
ebből következik, hogy
limp0+p1+...+pmm+1=1q1h1+...+qdhd.

Ismeretes, hogy ha pn konvergens, akkor limp0+p1+...+pmm+1 is konvergens és ugyanoda tart, ezért a (pn) sorozat határértéke csak 1q1h1+...+qdhdlehet.
 Pataki János, Duino (Olaszország)