Kezdőlap


Feladat:	N.59	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor , Dombi Gergely , Gyarmati Katalin , Izsák Ferenc , Makai Márton , Méder Áron , Perényi Márton , Póczos Barnabás , Szádeczky-Kardoss Szabolcs , Valkó Benedek
Füzet:	1995/december, 539 - 540. oldal		PDF file
Témakör(ök):	Klasszikus valószínűség, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/február: N.59

Egy áramköri lapon a

P

Q

R

S

chip-eket minden lehetséges módon vezeték köti össze. Gazdaságossági okokból a

Q S

vezeték alul halad, a többiek felül. Egy elektron bolyongásra indul a

P

-ből oly módon, hogy útja során minden chip-nél egyenlő valószínűséggel választ a lehetséges

3

irány közül. Mekkora a valószínűsége annak, hogy az elektron először csak az

1995

. lépésben kerül az áramköri lap alsó oldalára?

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.

Az elektron pontosan akkor kerül először csak az 1995-ik lépésben az áramköri lap alsó oldalára, ha az első 1994 lépéssel a $Q$ vagy az $S$ chip-be jut el anélkül, hogy a $Q S$ vezetéken áthaladna, majd az 1995-ik lépésben teszi meg a $Q S$ utat. Ha tehát rendre $p_{i}$ , $q_{i}$ , $r_{i}$ , $s_{i}$ jelöli annak a valószínűségét, hogy az elektron az első $i$ lépésben a $Q S$ út elkerülésével a $P$ , $Q$ , $R$ , $S$ chip-be jut el, akkor a feladatban keresett valószínűséget $(q_{1994} + s_{1994}) / 3$ adja meg. Nyilván

\begin{matrix} p_{0} = 1, q_{0} = 0, r_{0} = 0, s_{0} = 0, \end{matrix}

továbbá a feltételes valószínűség tétele szerint

\begin{matrix} p_{i + 1} = \frac{q_{i} + r_{i} + s_{i}}{3}, q_{i + 1} = \frac{p_{i} + r_{i}}{3}, r_{i + 1} = \frac{p_{i} + q_{i} + s_{i}}{3}, s_{i + 1} = \frac{p_{i} + r_{i}}{3} . \end{matrix}

Célszerű bevezetni az

a_{i} = p_{i} + r_{i}

b_{i} = q_{i} + s_{i}

jelöléseket, ezekkel ugyanis a keresett valószínűség

b_{1994} / 3

, továbbá a fentiekből

\begin{matrix} a_{0} = 1 és b_{0} = 0, illetve a_{i + 1} = \frac{a_{i} + 2 b_{i}}{3} és b_{i + 1} = \frac{2 a_{i}}{3} . \end{matrix}

Innen

a_{i}

-re az

a_{i + 1} = \frac{1}{3} a_{i} + \frac{4}{9} a_{i - 1}

lineáris rekurzió adódik az

a_{0} = 1

és

a_{1} = \frac{1}{3}

kezdőértékkel. Az

a_{i}

-t keressük

c_{1} x_{1}^{i} + c_{2} x_{2}^{i}

alakban alkalmas

c_{1}

és

c_{2}

konstansokkal és az

x^{2} = \frac{1}{3} x + \frac{4}{9}

egyenlet

x_{1, 2}

gyökeivel, hiszen minden ilyen alakú sorozat kielégíti a rekurzió egyenletét. A kezdőértékekből a konstansokra egy lineáris egyenletrendszer adódik, amely egyértelműen megoldható; végeredményben azt kapjuk, hogy

\begin{matrix} a_{i} = \frac{3}{\sqrt[]{17}} [{(\frac{1 + \sqrt[]{17}}{6})}^{i + 1} - {(\frac{1 - \sqrt[]{17}}{6})}^{i + 1}] . \end{matrix}

Így a feladatban kérdezett valószínűség

\begin{matrix} P = \frac{b_{1994}}{3} = \frac{2 a_{1993}}{9} = \frac{2}{3 \sqrt[]{17}} [{(\frac{1 + \sqrt[]{17}}{6})}^{1994} - {(\frac{1 - \sqrt[]{17}}{6})}^{1994}] = 2,42 ... \cdot 10^{- 138} . \end{matrix}

Makai Márton (Debrecen, Fazekas M. Gimn., III. o.t.) dolgozata alapján