Feladat: A.592 Korcsoport: 18- Nehézségi fok: nehéz
Kitűző(k):  Csóka Endre 
Füzet: 2013/május, 293. oldal  PDF file
Témakör(ök): Nehéz feladat, Fagráfok, erdők, faváz, Logikai feladatok, Valószínűségi változó

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.

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 limnp(n) értékét.