Problem A. 592. (May 2013)
A. 592. Color the vertices of a binary tree of depth 22n as follows. In the initial position let all vertices be white. Take the vertices one by one in a random order. Color the current vertex to red, except if from that vertex there starts a path of length n downwards (away from the root), whose other vertices are already red. Let p(n) be the probability that during the procedure, the root remains white. Determine .
Proposed by Endre Csóka
(5 pont)
Deadline expired on June 10, 2013.
Sorry, the solution is available only in Hungarian. Google translation
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 kn, akkor p(k,m)p(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 kn, 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)[1/4,1/4+1/n].
Statistics:
0 student sent a solution.
Problems in Mathematics of KöMaL, May 2013