Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 \lim_{n\to\infty} p(n).

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 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].


Statistics:

0 student sent a solution.

Problems in Mathematics of KöMaL, May 2013