 |
Az A. 846. feladat (2023. február) |
A. 846. Legyen \(\displaystyle n\) egy pozitív egész szám, és legyenek adva a \(\displaystyle v_1,v_2,\ldots,v_n\) vektorok a síkon. Az origóból indulva egy bolha a következő szabály szerint ugrál: \(\displaystyle i=1,2,\ldots,n\) esetén az \(\displaystyle i\). percben \(\displaystyle 1/2\) eséllyel ott marad, ahol éppen van, \(\displaystyle 1/4\) eséllyel a \(\displaystyle v_i\) vektorral ugrik arrébb, \(\displaystyle 1/4\) eséllyel pedig a \(\displaystyle -v_i\) vektorral ugrik arrébb. Bizonyítandó, hogy az \(\displaystyle n\). perc után nincs olyan pont, ahol nagyobb valószínűséggel tartózkodik a bolha, mint az origóban.
Javasolta: Pach Péter Pál (Budapest)
(7 pont)
A beküldési határidő 2023. március 10-én LEJÁRT.
Tegyük fel, hogy az \(\displaystyle i\)-edik percben a bolha először eldönti \(\displaystyle \frac{1}{2}\) eséllyel, hogy ugorjon-e a \(\displaystyle v_i\) vektorral, majd ettől függetlenül eldönti \(\displaystyle \frac{1}{2}\) eséllyel, hogy ugorjon-e a \(\displaystyle -v_i\) vektorral. Ez éppen azt eredményezi, hogy összesen a perc során \(\displaystyle \frac{1}{4}\) eséllyel ugrik \(\displaystyle v_i\)-it illetve \(\displaystyle -v_i\)-t, és \(\displaystyle \frac{1}{4}+\frac{1}{4}=\frac{1}{2}\) eséllyel helyben marad.
Az ugrások sorrendje lényegtelen abból a szempontból, hogy hol áll a bolha az \(\displaystyle n\)-edik perc végén, így azt is feltehetjük, hogy először dönt minden \(\displaystyle v_i\) vektorokról, ezt nevezzük az első menetnek. Aztán minden \(\displaystyle -v_i\) vektorról is dönt a bolha, hogy ugorjon-e vele, ezt nevezzük a második menetnek.
Legyen \(\displaystyle W\) azon vektorok halmaza, amikkel a bolha összesen elmozdulhatott az első menetben. \(\displaystyle w\in W\)-re legyen annak a valószínűsége, hogy \(\displaystyle w\)-vel mozdult el, \(\displaystyle p_w\).
A második menetben a bolha \(\displaystyle -W=\{-w: w\in W\}\)-beli vektorokkal mozdulhat el, és a \(\displaystyle -w\)-vel való elmozdulás valószínűsége \(\displaystyle p_w\), mivel minden útvonalnak, ahogy az első menetben \(\displaystyle w\)-t haladhatott, egyértelműen megfelel egy ugyanannyi ugrásból álló útvonal, amivel a második menetben \(\displaystyle -w\)-t haladhatott.
Tehát tetszőleges \(\displaystyle r\) vektorra annak a valószínűsége, hogy a bolha az egész mozgása során az \(\displaystyle r\) vektorral mozdul el az origóból,
\(\displaystyle \sum_{w_1, w_2\in W, w_1-w_2=r} p_{w_1}p_{w_2}.\)
Mivel minden \(\displaystyle w_1\in W\)-re legfeljebb egy \(\displaystyle w_2\in W\) vektor van, amire \(\displaystyle w_1-w_2=r\), ezért a fenti szumma kisebb-egyenlő mint egy
\(\displaystyle \sum_{w\in W} p_wp_{\pi(w)}\)
szumma, ahol \(\displaystyle \pi\) egy permutációja \(\displaystyle W\) elemeinek. A rendezési tétel szerint ez kisebb-egyenlő, mint \(\displaystyle \sum_{w\in W} p_w^2.\)
Márpedig az, hogy végül az origóban lesz a bolha, az éppen azt jelenti, hogy a második menetben az ellentétes vektorral mozdul el mint az első menetben, aminek a valószínűsége éppen \(\displaystyle \sum_{w\in W} p_w^2.\)
Ezzel az állítást beláttuk.
Statisztika:
6 dolgozat érkezett. 7 pontot kapott: Németh Márton, Seres-Szabó Márton, Varga Boldizsár. 0 pontot kapott: 3 versenyző.
A KöMaL 2023. februári matematika feladatai