|
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 | MathML |
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 |
|
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 definícióját -ra a következőképpen: (Ezeknek teljesen szemléletes jelentése van.) Világos, hogy az -edik mezőre az -edik, -edik, -adik és -edik mezőről léphetünk, a megfelelő utolsó dobás valószínűsége , ezért a teljes valószínűség tétele alapján | | vagyis | | (2) | E sorozat karakterisztikus polinomja: | |
Legyenek a egyenlet gyökei, ideértve a komplexeket is, , , , , multiplicitásuk rendre , , , , azaz gyöktényezős alakja | | Ismeretes, hogy a sorozat -edik eleme | | (3) | alakú, ahol (, 2, , ) valamilyen -nél alacsonyabb fokú polinom; és megfordítva, ha a sorozat ilyen alakú, akkor igaz rá a rekurzió. A polinom egyik gyöke az , és ez csak egyszeres gyök, mert | | (4) | és a második tényezőnek az nem gyöke. A többi gyök abszolút értékben -nél kisebb, mert esetén , és egyenlőség csak akkor van, ha . Így konstans polinom, és a (3) többi tagja zérushoz tart, ha tart a végtelenhez. Most meghatározzuk -et, ami az előbbiek alapján a sorozat határértéke. Definiáljuk a sorozatot a következőképpen: | | (5) | A sorozatra (4) miatt fennáll, hogy | | azaz | | Behelyettesítve -t, | | amiből . Tehát Megbecsüljük a konvergencia sebességét. Mivel | | a sorozatra a | | rekurzió is teljesül. Ebből következik, hogy | |
Bebizonyítjuk, hogy . Ez , , , 0 esetén könnyen ellenőrizhető. Ha pedig igaz esetén (, 2, ), akkor | |
Ha -at behelyettesítünk, akkor | | vagyis Megjegyzések. 1. Ha lapú dobókockával dobunk, azaz egyforma valószínűséggel lépünk 1, 2, , vagy mezőt, akkor is megoldható a feladat. (-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 annak valószínűsége, hogy rálépünk az -edik mezőre és legyen , . Ekkor világos, hogy esetén vagyis | | Most | | Ennek egyik gyöke , a többi gyök abszolút értéke -nél kisebb. A multiplicitása, , mert | | és a második tényező esetén pozitív. A sorozatra teljesül, hogy | | azaz | | Behelyettesítve -t, | | amiből Tehát A megbecsüléséhez: | | amiből -re | | ahonnan | | Innen pedig | | Ez a becslés -hoz tart esetén. (Ha , akkor az állítás triviális. Ha , akkor és .)
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 | | (7) | azonosságot. Ez -ra, mint láttuk, igaz. Ha pedig igaz -re, akkor | | Ezzel (7)-et igazoltuk. Írjuk fel (7)-et -re is: | | (8) | Vonjuk ki (7)-ből (8) -szorosát: | |
Ezzel az összes szükséges azonosságot igazoltuk. 3. Tegyük fel, hogy a lehetséges lépéshosszok a pozitív egészek, ezek valószínűsége . Legyen továbbra is annak valószínűsége, hogy rálépünk az -edik mezőre. Bebizonyítjuk, hogy ha a sorozat konvergens, akkor határértéke | | (Azt nem nehéz bebizonyítani, hogy akkor konvergens, ha a számoknak nincs -nél nagyobb közös osztója.) Definiáljuk az véletlen mennyiségeket (valószínűségi változókat) a következőképpen: | |
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 Ebből következik, hogy az összeg várható értéke is e két határ között van: | m+1≤E(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)=pnq1⋅h1+pnq2⋅h2+...+pnqd⋅hd=pn(q1h1+...+qdhd), | ez azt jelenti, hogy | m+1≤(p0+p1+...+pm)(q1h1+...+qdhd)≤m+hd, | amit (m+1)(q1h1+...+qdhd)-vel osztva | 1q1h1+...+qdhd≤p0+p1+...+pmm+1≤(1+hd-1m+1)1q1h1+...+qdhd. | Mivel m→∞ esetén 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) |
|
|