Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

A. 592. Egy 22n 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)2+p(0,m).

Ha k\gen, akkor p(k,m)\lep(k-1,m-1)2+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 (2n-2)s/s!, ami 0-hoz tart.

Bizonyítás. (2n-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=22n/4, m>22n/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 22n és egy 22n-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)2+p(0),

Ha k\gen, akkor p(k)<=p(k-1)2+p(0).

Mivel az x2-x függvény minimuma (1/2)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