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. Márciusi feladványunk beküldői közül a FORTUNA magazin 1 éves előfizetését nyerte
Csere Kálmán balatonboglári olvasónk. Áprilisi játékunk a ,,Ki nevet a végén'' volt: Mekkora eséllyel fogunk pontosan a 100. mezőre lépni, ha egy dobókockával játszunk (és eltekintünk a kiütéstől)?
Egyetlen helyes megoldónk Bereczkiné Székely Erzsébet volt. Megoldása: Jelölje annak az esélyét, hogy az . mezőre rálépünk. Hogyan következhet ez be? Az utolsó dobástól függően 6 eset lehetséges, mindegyik egyforma eséllyel, ha a kockánk ,,szabályos''. Eszerint, a teljes valószínűség tételét felhasználva az alábbi rekurzív összefüggést írhatjuk fel:
| |
Ha tehát az első hat mező esélyét fel tudnánk írni, akkor utána ez az összefüggés már meghatározza az összes többi mezőre lépés esélyét. , hiszen csak akkor lépek az első mezőre, ha 1-est dobok. , hiszen vagy egy ugrással (2-est dobok), vagy két 1-es dobással lehet ezt a mezőt elérni. általában , ahol . Ezután egy számítógéppel pillanatok alatt meg lehet határozni, hogy , azaz . Minél nagyobb a mező sorszáma, annál közelebb lesz a -hez, ez lesz a sorozat határértéke.
Megjegyzés. Érdeklődő olvasóink kedvéért vázoljuk annak bizonyítását, hogy a sorozat -hez tart. A bizonyítás a lineáris rekurzív sorozatok általános képletére épít, de a lépések e tétel nélkül is elvégezhetők teljes indukcióval. A sorozat egy úgynevezett lineáris rekurzív sorozat, amelyre teljesül a
| |
azonosság. Ismeretes, hogy egy ilyen sorozat -edik tagját explicit alakban a
| |
polinom gyökeinek segítségével lehet felírni. Ezt a polinomot a sorozat karakterisztikus polinomjának is nevezik. Ha a polinom (valós és komplex) gyökei , multiplicitásuk , azaz a polinom gyöktényezős alakja
| |
akkor a sorozat -edik eleme
| |
alakú, akol valamilyen -nél alacsonyabb fokú polinom, és megfordítva: ha a sorozat ilyen alakú, akkor teljesül rá a rekurzió. Esetünkben egyik gyöke (legyen ez ) az 1, és ez egyszeres gyök:
| |
A többi gyök 1-nél kisebb abszolút értékű, mert esetén , és egyenlőség csak akkor van, ha . Mindezekből következik, hogy konstans polinom, és (1) többi tagja 0-hoz tart. A feladat tehát meghatározása lehetőleg a többi gyök kiszámítása nélkül (ami gyakorlatilag lehetetlen). Legyen Erre a sorozatra a fentiek szerint teljesül a rekurzió. Mivel , , , , , , ebből egy egyenletet kapunk -re:
Rendezve: , azaz . Ha nem akarunk törtekkel számolni, a sorozatot visszafelé, nem povitív indexekre is kiterjeszthetjük:
| |
és ezáltal
| |
Most megbecsülhetjük a konvergencia sebességét. Mivel
| |
a sorozatra teljesül a
| |
rekurzió. Következésképp a , amiből nem nehéz teljes indukcióval bebizonyítani, hogy . Ezzel például -ra az becslést kapjuk, azaz már csak a 8-adik tizedesjegyben térhet el a -től.
Arra, hogy a sorozat határértéke miért éppen , nem nehéz heurisztikus meggondolást adni. A lépések egyforma valószínűséggel 1, 2, 3, 4, 5 vagy 6 hosszúságúak, egy ,,átlagos'' lépés hossza tehát 3,5. Ez pedig azt jelenti, hogy a mezőknek ,,átlagosan'' a részére lépünk rá, tehát egy mezőre körülbelül valószínűséggel.
|