Kezdőlap


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 $p_{n}$ definícióját $n = 0, - 1, - 2, - 3$ -ra a következőképpen:

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

(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

\frac{1}{4}

, ezért a teljes valószínűség tétele alapján

\begin{matrix} p_{n} = \frac{1}{4} p_{n - 1} + \frac{1}{4} p_{n - 2} + \frac{1}{4} p_{n - 3} + \frac{1}{4} p_{n - 4} (n = 1,2, ...), \end{matrix}

vagyis

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

(2)

E sorozat karakterisztikus polinomja:

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

Legyenek a

p (x) = 0

egyenlet gyökei, ideértve a komplexeket is,

z_{1}

z_{2}

...

z_{k}

, multiplicitásuk rendre

α_{1}

α_{2}

...

α_{k}

, azaz

p (x)

gyöktényezős alakja

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

Ismeretes, hogy a

(p_{n})

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}

(3)

alakú, ahol

a_{i} (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

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

(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 | \geq 1

esetén

| p (x) | \geq | x |^{4} - | x |^{3} \geq 0

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

x = 1

. Így

a_{1}

konstans polinom, és a (3) többi tagja zérushoz tart, ha

n

tart a végtelenhez.
Most meghatározzuk

a_{1}

-et, ami az előbbiek alapján a

p_{n}

sorozat határértéke. Definiáljuk a

q_{n}

sorozatot a következőképpen:

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

(5)

q_{n}

sorozatra (4) miatt fennáll, hogy

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

azaz

\begin{matrix} (p_{n} - a_{1}) + \frac{3}{4} (p_{n - 1} - a_{1}) + \frac{1}{2} (p_{n - 2} - a_{1}) + \frac{1}{4} (p_{n - 3} - a_{1}) = 0. \end{matrix}

Behelyettesítve

n = 0

-t,

\begin{matrix} (1 - a_{1}) + \frac{3}{4} (0 - a_{1}) + \frac{1}{2} (0 - a_{1}) + \frac{1}{4} (0 - a_{1}) = 0, \end{matrix}

amiből

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

. Tehát

\begin{matrix} {lim}_{}^{} p_{n} = \frac{2}{5} . \end{matrix}

(6)

Megbecsüljük a konvergencia sebességét. Mivel

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

q_{n}

sorozatra a

\begin{matrix} q_{n} + \frac{1}{12} q_{n - 1} - \frac{1}{12} q_{n - 3} - \frac{1}{6} q_{n - 4} \end{matrix}

rekurzió is teljesül. Ebből következik, hogy

\begin{matrix} | q_{n} | \leq \frac{1}{12} | q_{n - 1} | + \frac{1}{12} | q_{n - 3} | + \frac{1}{6} | q_{n - 4} | \leq \frac{1}{3} {max}_{}^{} (| q_{n - 1} |, | q_{n - 3} |, | q_{n - 4} |) . \end{matrix}

Bebizonyítjuk, hogy

| q_{n} | \leq {(\frac{1}{3})}^{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

\begin{matrix} | q_{m} | \leq \frac{1}{3} {max}_{}^{} (| q_{m - 1} |, | q_{m - 3} |, | q_{m - 4} |) \leq \frac{1}{3} \cdot {(\frac{1}{3})}^{\frac{m - 4}{4}} = {(\frac{1}{3})}^{\frac{m}{4}} . \end{matrix}

n = 100

-at behelyettesítünk, akkor

\begin{matrix} | q_{100} | = | p_{100} - a_{1} | = | p_{100} - 0, 4 | \leq {(\frac{1}{3})}^{25} < 10^{- 6}, \end{matrix}

vagyis

\begin{matrix} 0, 399 999 < p_{100} < 0, 400 001. \end{matrix}

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

p_{n}

annak valószínűsége, hogy rálépünk az

n

-edik mezőre és legyen

p_{0} = 1

p_{- 1} = p_{- 2} = ... = p_{- d} = 0

.
Ekkor világos, hogy

n = 0,1, ...

esetén

\begin{matrix} p_{n} = \sum_{i = 1}^{d} \frac{1}{d} p_{n - i}, \end{matrix}

vagyis

\begin{matrix} p_{n} - \frac{1}{d} p_{n - 1} - \frac{1}{d} p_{n - 2} - ... - \frac{1}{d} p_{n - d} = 0. \end{matrix}

Most

\begin{matrix} p (x) = x^{d} - \frac{1}{d} x^{d - 1} - \frac{1}{d} x^{d - 2} - ... - \frac{1}{d} . \end{matrix}

Ennek egyik gyöke

z_{1} = 1

, a többi gyök abszolút értéke

1

-nél kisebb. A

z_{1} = 1

multiplicitása,

α_{1} = 1

, mert

\begin{matrix} p (x) = (x - 1) (x^{d - 1} + \frac{d - 1}{d} x^{d - 2} + \frac{d - 2}{d} x^{d - 3} + ... + \frac{1}{d}), \end{matrix}

és a második tényező

x = 1

esetén pozitív.
A

q_{n} = p_{n} - a_{1}

sorozatra teljesül, hogy

\begin{matrix} q_{n} + \frac{d - 1}{d} q_{n - 1} + \frac{d - 2}{d} q_{n - 2} + ... + \frac{1}{d} q_{n - d} = 0, \end{matrix}

azaz

\begin{matrix} (p_{n} - a_{1}) + \frac{d - 1}{d} (p_{n - 1} - a_{1}) + \frac{d - 2}{d} (p_{n - 2} - a_{1}) + ... + \frac{1}{d} (p_{n - d} - a_{1}) = 0. \end{matrix}

Behelyettesítve

n = 0

-t,

\begin{matrix} (1 - a_{1}) + \frac{d - 1}{d} (0 - a_{1}) + \frac{d - 2}{d} (0 - a_{1}) + ... + \frac{1}{d} (0 - a_{1}) = 0, \end{matrix}

amiből

\begin{matrix} a_{1} = \frac{1}{\frac{1}{d} + \frac{2}{d} + ... + \frac{d}{d}} = \frac{2}{d + 1} . \end{matrix}

Tehát

\begin{matrix} {lim}_{}^{} p_{n} = \frac{2}{d + 1} . \end{matrix}

| q_{n} |

megbecsüléséhez:

\begin{matrix} \begin{matrix} (x - \frac{d - 2}{d - 1}) (x^{d - 1} + \frac{d - 1}{d} x^{d - 2} + \frac{d - 2}{d} x^{d - 3} + ... + \frac{1}{d}) = \\ = x^{d} + \frac{1}{d (d - 1)} x^{d - 1} - \frac{1}{d (d - 1)} x^{d - 3} - \frac{2}{d (d - 1)} x^{d - 4} - ... - \frac{d - 2}{d (d - 1)}, \end{matrix} \end{matrix}

amiből

q_{n}

-re

\begin{matrix} q_{n} + \frac{1}{d (d - 1)} q_{n - 1} - \frac{1}{d (d - 1)} q_{n - 3} - \frac{2}{d (d - 1)} q_{n - 4} - ... - \frac{d - 2}{d (d - 1)} q_{n - d} = 0, \end{matrix}

ahonnan

\begin{matrix} \begin{matrix} | q_{n} | \leq \frac{1 + 1 + 2 + ... + (d - 2)}{d (d - 1)} {max}_{}^{} (| q_{n - 1} |, | q_{n - 3} |, ..., | q_{n - d} |) < \\ < (1 - \frac{2 d - 4}{d (d - 1)}) {max}_{}^{} (| q_{n - 1} |, | q_{n - 3} |, ..., | q_{n - d} |) . \end{matrix} \end{matrix}

Innen pedig

\begin{matrix} | p_{n} - \frac{2}{d + 1} | = | q_{n} | \leq {(1 - \frac{2 d - 4}{d (d - 1)})}^{\frac{n}{d}} . \end{matrix}

Ez a becslés

0

-hoz tart

d \geq 3

esetén. (Ha

d = 1

, akkor az állítás triviális. Ha

d = 2

, akkor

z_{2} = - \frac{1}{2}

és

| q_{n} | = {(\frac{1}{2})}^{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

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

(7)

azonosságot. Ez

n = 0

-ra, mint láttuk, igaz. Ha pedig igaz

n = m - 1

-re, akkor

\begin{matrix} \begin{matrix} (p_{m} - \frac{2}{5}) + \frac{3}{4} (p_{m - 1} - \frac{2}{5}) + \frac{1}{2} (p_{m - 2} - \frac{2}{5}) + \frac{1}{4} (p_{m - 3} - \frac{2}{5}) = \\ = (p_{m} - \frac{2}{5}) + \frac{3}{4} (p_{m - 1} - \frac{2}{5}) + \frac{1}{2} (p_{m - 2} - \frac{2}{5}) + \frac{1}{4} (p_{m - 3} - \frac{2}{5}) - \\ - (p_{m} - \frac{1}{4} p_{m - 1} - \frac{1}{4} p_{m - 2} - \frac{1}{4} p_{m - 3} - \frac{1}{4} p_{m - 4}) = \\ = (p_{m - 1} - \frac{2}{5}) + \frac{3}{4} (p_{m - 2} - \frac{2}{5}) + \frac{1}{2} (p_{m - 3} - \frac{2}{5}) + \frac{1}{4} (p_{m - 4} - \frac{2}{5}) = 0. \end{matrix} \end{matrix}

Ezzel (7)-et igazoltuk. Írjuk fel (7)-et

n - 1

-re is:

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

(8)

Vonjuk ki (7)-ből (8)

\frac{2}{3}

-szorosát:

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

Ezzel az összes szükséges azonosságot igazoltuk.
3. Tegyük fel, hogy a lehetséges lépéshosszok a

h_{1} < ... < h_{d}

pozitív egészek, ezek valószínűsége

q_{1}, ..., q_{d} > 0

. Legyen

p_{n}

továbbra is annak valószínűsége, hogy rálépünk az

n

-edik mezőre. Bebizonyítjuk, hogy ha a

p_{n}

sorozat konvergens, akkor határértéke

\begin{matrix} {lim}_{}^{} p_{n} = \frac{1}{q_{1} h_{1} + q_{2} h_{2} + ... + q_{d} h_{d}} . \end{matrix}

(Azt nem nehéz bebizonyítani, hogy

p_{n}

akkor konvergens, ha a

h_{1}, ..., h_{d}

számoknak nincs

1

-nél nagyobb közös osztója.)
Definiáljuk az

X_{0}, X_{1}, ...

véletlen mennyiségeket (valószínűségi változókat) a következőképpen:

\begin{matrix} X_{n} = {\begin{matrix} 0, & ha azn-edik mezőre nem lépünk rá; \\ i, & ha azn-edik mezőre rálépünk és otti-t dobunk. \end{matrix} \end{matrix}

Ekkor

X_{0} + X_{1} + ... + X_{m}

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 + h_{d}

között van, tehát

\begin{matrix} m + 1 \leq X_{0} + X_{1} + ... + X_{m} \leq m + h_{d} . \end{matrix}

Ebből következik, hogy az összeg várható értéke is e két határ között van:

\begin{matrix} m + 1 \leq E (X_{0} + X_{1} + ... + X_{m}) = E (X_{0}) + E (X_{1}) + ... + E (X_{m}) \leq m + h_{d} . \end{matrix}

(A várható értéket mindig lehet tagonként számolni.)
Mivel

\begin{matrix} E (X_{n}) = p_{n} q_{1} \cdot h_{1} + p_{n} q_{2} \cdot h_{2} + ... + p_{n} q_{d} \cdot h_{d} = p_{n} (q_{1} h_{1} + ... + q_{d} h_{d}), \end{matrix}

ez azt jelenti, hogy

\begin{matrix} m + 1 \leq (p_{0} + p_{1} + ... + p_{m}) (q_{1} h_{1} + ... + q_{d} h_{d}) \leq m + h_{d}, \end{matrix}

amit

(m + 1) (q_{1} h_{1} + ... + q_{d} h_{d})

-vel osztva

\begin{matrix} \frac{1}{q_{1} h_{1} + ... + q_{d} h_{d}} \leq \frac{p_{0} + p_{1} + ... + p_{m}}{m + 1} \leq (1 + \frac{h_{d} - 1}{m + 1}) \frac{1}{q_{1} h_{1} + ... + q_{d} h_{d}} . \end{matrix}

Mivel

m \to \infty

esetén

\begin{matrix} (1 + \frac{h_{d} - 1}{m + 1}) \to 1, \end{matrix}

ebből következik, hogy

\begin{matrix} {lim}_{}^{} \frac{p_{0} + p_{1} + ... + p_{m}}{m + 1} = \frac{1}{q_{1} h_{1} + ... + q_{d} h_{d}} . \end{matrix}

Ismeretes, hogy ha

p_{n}

konvergens, akkor

{lim}_{}^{} \frac{p_{0} + p_{1} + ... + p_{m}}{m + 1}

is konvergens és ugyanoda tart, ezért a

(p_{n})

sorozat határértéke csak

\frac{1}{q_{1} h_{1} + ... + q_{d} h_{d}}

lehet.

Pataki János, Duino (Olaszország)