Kezdőlap


Cím:	Játék mindenkinek
Szerző(k):	Kós Géza , Vancsó Ödön
Füzet:	1994/november, 430 - 432. oldal	PDF \| MathML
Témakör(ök):	Egyéb (KöMaL pontverseny is)

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

P_{n}

annak az esélyét, hogy az

n

. 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:

\begin{matrix} p_{n} = \frac{1}{6} p_{n - 1} + \frac{1}{6} p_{n - 2} + \frac{1}{6} p_{n - 3} + \frac{1}{6} p_{n - 4} + \frac{1}{6} p_{n - 5} + \frac{1}{6} p_{n - 6} . \end{matrix}

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.

p_{1} = \frac{1}{6}

, hiszen csak akkor lépek az első mezőre, ha 1-est dobok.

p_{2} = \frac{1}{6} + \frac{1}{36} = \frac{1}{6} \cdot \frac{7}{6}

, hiszen vagy egy ugrással (2-est dobok), vagy két 1-es dobással lehet ezt a mezőt elérni.

p_{3} = \frac{1}{6} + \frac{2}{36} + \frac{1}{216} = \frac{1}{6} \cdot {(\frac{7}{6})}^{2}, ...,

általában

p_{i} = \frac{1}{6} \cdot {(\frac{7}{6})}^{i - 1}

, ahol

i = 1,2, ...,6

.
Ezután egy számítógéppel pillanatok alatt meg lehet határozni, hogy

p_{100} \approx 0,28571

, azaz

\approx 2 / 7

.
Minél nagyobb a mező sorszáma, annál közelebb lesz

p_{n}

2 / 7

-hez, ez lesz a

p_{n}

sorozat határértéke.

Vancsó Ödön

⋆

Megjegyzés. Érdeklődő olvasóink kedvéért vázoljuk annak bizonyítását, hogy a

{p_{n}}

sorozat

2 / 7

-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

{p_{n}}

sorozat egy úgynevezett lineáris rekurzív sorozat, amelyre teljesül a

\begin{matrix} p_{n + 6} - \frac{1}{6} p_{n + 5} - \frac{1}{6} p_{n + 4} - \frac{1}{6} p_{n + 3} - \frac{1}{6} p_{n + 2} - \frac{1}{6} p_{n + 1} - \frac{1}{6} p_{n} = 0 \end{matrix}

azonosság. Ismeretes, hogy egy ilyen sorozat

n

-edik tagját explicit alakban a

\begin{matrix} p (x) = x^{6} - \frac{1}{6} x^{5} - \frac{1}{6} x^{4} - \frac{1}{6} x^{3} - \frac{1}{6} x^{2} - \frac{1}{6} x - \frac{1}{6} \end{matrix}

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

z_{1}, z_{2}, ..., z_{k}

, multiplicitásuk

α_{1}, α_{2}, ..., α_{k}

, azaz a polinom gyöktényezős alakja

\begin{matrix} {(x - z_{1})}^{α_{1}} {(x - z_{2})}^{α_{2}} ... {(x - z_{k})}^{α_{k}}, \end{matrix}

akkor a sorozat

n

-edik eleme

\begin{matrix} p_{n} = a_{1} (n) z_{1}^{n} + a_{2} (n) z_{2}^{n} + ... + a_{k} (n) z_{k}^{n} \end{matrix}

alakú, akol

a_{i} (n)

valamilyen

α_{i}

-nél alacsonyabb fokú polinom, és megfordítva: ha a sorozat ilyen alakú, akkor teljesül rá a rekurzió.
Esetünkben

p

egyik gyöke (legyen ez

z_{1}

) az 1, és ez egyszeres gyök:

\begin{matrix} p (x) = (x - 1) (x^{5} + \frac{5}{6} x^{4} + \frac{4}{6} x^{3} + \frac{3}{6} x^{2} + \frac{2}{6} x + \frac{1}{6}) . \end{matrix}

A többi gyök 1-nél kisebb abszolút értékű, mert

| x | \geq 1

esetén

| p (x) | \geq | x |^{6} - | x |^{5} \geq 0

, és egyenlőség csak akkor van, ha

x = 1

. Mindezekből következik, hogy

a_{1}

konstans polinom, és (1) többi tagja 0-hoz tart. A feladat tehát

a_{1}

meghatározása lehetőleg a többi gyök kiszámítása nélkül (ami gyakorlatilag lehetetlen).
Legyen

q_{n} = a_{2} (n) z_{2}^{2} + ... + a_{k} (n) z_{k}^{2} = p_{n} - a_{1} .

Erre a sorozatra a fentiek szerint teljesül a

q_{n + 5} + \frac{5}{6} q_{n + 4} + \frac{4}{6} q_{n + 3} + \frac{3}{6} q_{n + 2} + \frac{2}{6} q_{n + 1} + \frac{1}{6} q_{n} = 0

rekurzió. Mivel

p_{1} = \frac{1}{6}

p_{2} = \frac{7}{36}

p_{3} = \frac{49}{216}

p_{4} = \frac{343}{1296}

p_{5} = \frac{2401}{7776}

p_{6} = \frac{16807}{46656}

, ebből egy egyenletet kapunk

a_{1}

-re:

\begin{matrix} (\frac{16807}{46656} - a_{1}) + \frac{5}{6} (\frac{2401}{7776} - a_{1}) + \frac{4}{6} (\frac{343}{1296} - a_{1}) + \\ + \frac{3}{6} (\frac{49}{216} - a_{1}) + \frac{2}{6} (\frac{7}{36} - a_{1}) + \frac{1}{6} (\frac{1}{6} - a_{1}) = 0 \end{matrix}

Rendezve:

1 - \frac{7}{2} a_{1} = 0

, azaz

a_{1} = \frac{2}{7}

.
Ha nem akarunk törtekkel számolni, a sorozatot visszafelé, nem povitív indexekre is kiterjeszthetjük:

\begin{matrix} p_{0} = 1, p_{- 1} = p_{- 2} = p_{- 3} = p_{- 4} = p_{- 5} = 0, \end{matrix}

és ezáltal

\begin{matrix} (1 - a_{1}) + \frac{5}{6} (0 - a_{1}) + \frac{4}{6} (0 - a_{1}) + \frac{3}{6} (0 - a_{1}) + \frac{2}{6} (0 - a_{1}) + \frac{1}{6} (0 - a_{1}) = 1 - \frac{7}{2} a_{1} = 0. \end{matrix}

Most megbecsülhetjük a konvergencia sebességét. Mivel

\begin{matrix} (x - \frac{4}{5}) (x^{5} + \frac{5}{6} x^{4} + \frac{4}{6} x^{3} + \frac{3}{6} x^{2} + \frac{2}{6} x + \frac{1}{6}) = x^{6} + \frac{1}{30} x^{5} - \frac{1}{30} x^{3} - \frac{2}{30} x^{2} - \frac{3}{30} x - \frac{4}{30}, \end{matrix}

{q_{n}}

sorozatra teljesül a

\begin{matrix} q_{n + 6} + \frac{1}{30} q_{n + 5} - \frac{1}{30} q_{n + 3} - \frac{2}{30} q_{n + 2} - \frac{3}{30} q_{n + 1} - \frac{4}{30} q_{n} = 0 \end{matrix}

rekurzió. Következésképp a

| q_{n + 6} | \leq \frac{11}{30} {max}_{}^{} (| q_{n} |, | q_{n + 1} |, ..., | q_{n + s} |)

, amiből nem nehéz teljes indukcióval bebizonyítani, hogy

| p_{n} - \frac{2}{7} | = | q_{n} | < {(\frac{11}{30})}^{\frac{n}{6}}

. Ezzel például

p_{100}

-ra az

| p_{100} - \frac{2}{7} | < {(\frac{11}{30})}^{\frac{50}{3}} < 10^{- 7}

becslést kapjuk, azaz

p_{100}

már csak a 8-adik tizedesjegyben térhet el a

2 / 7

-től.

⋆

Arra, hogy a sorozat határértéke miért éppen

2 / 7

, 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

\frac{2}{7}

részére lépünk rá, tehát egy mezőre körülbelül

\frac{2}{7}

valószínűséggel.

Kós Géza