Az A. 592. feladat (2013. május)

A. 592. Egy 2^2ⁿ mélységű bináris fa csúcsait kiszínezzük a következő módon. Legyen kezdetben minden csúcs fehér. Vegyük a csúcsoknak egy véletlen sorrendjét, és a soron következő csúcsot színezzük mindig pirosra, kivéve, ha indul belőle lefelé (a gyökértől távolodva) olyan n hosszú út, melynek a többi csúcsa már mind piros. Jelölje p(n) annak valószínűségét, hogy az eljárás során a gyökér fehér maradt. Határozzuk meg $\lim_{n\to\infty} p(n)$ értékét.

Javasolta: Csóka Endre

(5 pont)

A beküldési határidő 2013. június 10-én LEJÁRT.

Megoldási ötletek. Jelölje p(k,m) annak a valószínűségét, hogy az eljárást m magas fában elvégezve a csúcsból lefele induló leghosszabb piros út hossza legfeljebb k hosszú lesz. A hossz 0, ha a csúcs fehér. Ekkor a gyökér két részfáját tekintve felírhatjuk a következőket:

Ha k<n, akkor p(k,m)=p(k-1,m-1)²+p(0,m).

Ha k $\ge$ n, akkor p(k,m) $\le$ p(k-1,m-1)²+p(0,m).

A következő ötlet az, hogy ha m nagy, akkor nem számít, hogy eggyel kisebb, vagy nagyobb. Ennek magyarázata a következő:

Függőségi láncnak nevezzük csúcsok egy olyan sorozatát, melyben minden csúcs az előző alatt van, de kevesebb, mint n távolságban, és minden csúcs előbb került sorra, mint az előző.

Lemma. Annak esélye, hogy a gyökérből indul s elemű függőségi lánc, kisebb, mint (2ⁿ-2)^s/s!, ami 0-hoz tart.

Bizonyítás. (2ⁿ-2)^s csúcssorozat lehet függőségi lánc, és mindnek 1/s! esélye van arra, hogy függőségi lánc legyen.

1. Következmény. Nagy k és még nagyobb m esetén (pl. k=2^2ⁿ/4, m>2^2ⁿ/2-re) p(k,m) értéke közelítőleg 1.

Bizonyítás. Egy hosszú piros út csak akkor jöhet létre, ha tartalmaz a gyökértől az aljáig érő függőségi láncot.

2. Következmény. Az eljárás egy 2^2ⁿ és egy 2^2ⁿ-1 magasságú fán nagy pontossággal ugyanolyan a gyökér közelében. A pontos hibabecslés mellőzésével nézzük meg, mit kapnánk, ha elhagynánk p második argumentumát:

Ha k<n, akkor p(k)=p(k-1)²+p(0),

Ha k $\ge$ n, akkor p(k)<=p(k-1)²+p(0).

Mivel az x²-x függvény minimuma (1/2)²-1/2=-1/4, ezért p(0)<1/4 esetén minden k-ra p(k)<1/2 maradna, ellenben p(0)>1/4+1/n esetén p(k)>p(k-1)+1/n miatt p(n)>1 lenne. Tehát p(0) $\in$ [1/4,1/4+1/n].

Statisztika:

0 dolgozat érkezett.

A KöMaL 2013. májusi matematika feladatai

Már regisztráltál?
Új vendég vagy?