KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 June 2013.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem A. 592.
0 student sent a solution.


  • Problems in Mathematics of KöMaL, May 2013

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley