Problem B. 5027. (April 2019)
B. 5027. Arthur Dumpling (Hungarian cartoon character: a fat bird who loves chocolate of all kinds) lives at 1 Sweet Street. The chocolate shop is operating at number \(\displaystyle n\), the far end of the street. Arthur's daily fitness programme is as follows: he starts in front of number 2. When he stands in front of number \(\displaystyle k\) (where \(\displaystyle 1<k<n\)), he tosses a fair chocolate coin. If it shows heads, he moves to number \(\displaystyle (k-1)\). If it shows tails, he moves to number \(\displaystyle (k+1)\). If he reaches the chocolate shop, he enters and throws a chocolate ball down his throat, and then moves to number \(\displaystyle (n-1)\). If he arrives back home, the fitness programme terminates. On average, how many chocolate balls does Arthur throw down his throat per day?
(5 pont)
Deadline expired on May 10, 2019.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Először megmutatjuk, hogy Gombóc Artúr 1 valószínűséggel hazaér. Bárhol is van éppen, legfeljebb \(\displaystyle n-2\) csokiérmedobáson belül legalább \(\displaystyle \frac{1}{2^{n-2}}\) valószínűséggel hazaér, hiszen ha mindig fejet dob, mindig közeledik otthonához. Ez azt jelenti, hogy annak valószínűsége, hogy \(\displaystyle (n-2)k\) dobás után még nincs otthon, legfeljebb \(\displaystyle \left(1- \frac{1}{2^{n-2}} \right)^k\), ami tart a 0-hoz, ha \(\displaystyle k\to \infty\). Tehát Gombóc Artúr 1 valószínűséggel hazaér, és befejezi az edzést.
Tekintsük az edzés során azokat a pillanatokat, amikor vagy a 2. számú ház előtt van, vagy épp csokizás után az \(\displaystyle (n-1).\) számú ház előtt. Jelölje \(\displaystyle p\) annak a valószínűségét, hogy Gombóc Artúr a 2. ház elől a csokibolthoz előbb jut el, mint haza. Ekkor, ha csokizás után az \(\displaystyle (n-1).\) számú ház előtt van, akkor a szimmetria alapján \(\displaystyle 1-p\) annak a valószínűsége, hogy még visszajut a csokiboltba hazaérés előtt.
Megjegyezzük, hogy \(\displaystyle 0<p<1\), hiszen világos, hogy \(\displaystyle \frac{1}{2^{n-2}}\leq p\leq \frac{1}{2}\), ugyanis 1 fej dobás esetén rögtön hazaér, illetve \(\displaystyle n-2\) írás dobás esetén biztosan eljut a csokiboltba hazaérés előtt.
Most rátérünk az átlagosan legurított csokigolyók számának meghatározására.
Annak valószínűsége, hogy Gombóc Artúr egyetlen csokigolyót sem eszik meg, éppen \(\displaystyle 1-p\). Annak valószínűsége, hogy pontosan 1-et eszik meg \(\displaystyle p^2\), hiszen \(\displaystyle p\) annak esélye, hogy a 2-es számú ház elől előbb jut a csokiboltba, mint haza, és annak is \(\displaystyle p\) az esélye, hogy ezután az \(\displaystyle (n-1).\) számú ház elől (ahova az 1. csoki után megy) előbb jut haza, mint hogy ismét visszaérne a boltba. Ehhez hasonlóan annak valószínűsége, hogy pontosan \(\displaystyle 2\leq k\) csokit eszik meg hazaérkezéséig \(\displaystyle p(1-p)^{k-1}p\), hiszen \(\displaystyle p\) eséllyel jut előbb a bolthoz (majd onnan az \(\displaystyle (n-1).\) számú ház elé), mint haza, ezután \(\displaystyle (k-1)\)-szer az \(\displaystyle (n-1).\) számú ház elől előbb kell a bolthoz érnie, mint haza, végül a \(\displaystyle k.\) csoki után előbb kell hazaérnie már, mint hogy ismét visszajutna a bolthoz.
Így az átlagosan elfogyasztott csokik száma a végtelen mértani sor összegképletét használva:
$$\begin{multline*} E=0\cdot (1-p)+1\cdot p^2+2\cdot p^2(1-p)+3\cdot p^2(1-p)^2+\dots=p^2\left[1+2(1-p)+3(1-p)^2+\dots \right]=\\ = p^2\left[(1+(1-p)+(1-p)^2+\dots)+((1-p)+(1-p)^2+\dots)+((1-p)^2+(1-p)^3+\dots)+\dots \right]=\\ =p^2 \left[\frac{1}{p}+(1-p)\cdot\frac{1}{p}+(1-p)^2\cdot\frac{1}{p}+\dots \right]=p^2\cdot\frac{1}{p}\cdot\frac{1}{p}=1. \end{multline*}$$Tehát Gombóc Artúr naponta átlagosan 1 csokit fogyaszt el.
1. Megjegyzés. Bár a végeredmény meghatározásához nem volt szükséges, meg is határozhatjuk \(\displaystyle p\) értékét. Jelölje \(\displaystyle 2\leq i\leq n-1\) esetén \(\displaystyle p_i\) annak a valószínűségét, hogy az \(\displaystyle i.\) számú húz elől Gombóc Artúr előbb ér a csokiboltba, mint haza. (Ekkor \(\displaystyle p=p_2\).)
Ha \(\displaystyle i=2\), akkor \(\displaystyle p_2=\frac{1}{2}p_3\), hiszen vagy hazaér (fej dobás) vagy a 3-es ház elé megy (írás dobás), egyforma eséllyel.
Ha \(\displaystyle 3\leq i\leq n-2\), akkor ehhez hasonlóan \(\displaystyle p_i=\frac{1}{2}p_{i-1}+\frac{1}{2}p_{i+1}\).
Végül, ha \(\displaystyle i=n-1\), akkor \(\displaystyle p_{n-1}=\frac{1}{2}p_{n-2}+\frac{1}{2}\), hiszen fej esetén az \(\displaystyle (n-2).\) számú ház elé megy, írás esetén pedig a csokiboltba.
A megadott egyenletek éppen azt fejezik ki, hogy \(\displaystyle 0,p_2,p_3,\dots,p_{n-1},1\) egy számtani sorozat, és így \(\displaystyle p_2=p=\frac{1}{n-1}\).
2. Megjegyzés. Az előbbi egyenletrendszert közvetlenül az elfogyasztott csokik számának várható értékére is felírhatjuk, \(\displaystyle E_i\)-vel jelölve a hazaérkezésig elfogyasztott csokik számának várható értékét abban az esetben, ha az \(\displaystyle i.\) számú ház elől indul (\(\displaystyle 2\leq i\leq n-1\)). Ekkor az egyenletek:
\(\displaystyle E_2=\frac{1}{2}E_3,\quad E_i=\frac{1}{2}E_{i-1}+\frac{1}{2}E_{i+1}\ (3\leq i\leq n-2),\quad E_{n-1}=\frac{1}{2}E_{n-2}+\frac{1}{2}(E_{n-1}+1).\)
Ez azt jelenti, hogy \(\displaystyle 0,E_2,E_3,\dots,E_{n-1},E_{n-1}+1\) egy számtani sorozat. Bevezetve \(\displaystyle E_2=E\)-t, rendre \(\displaystyle E_3=2E,E_4=3E,\dots,E_{n-1}=(n-2)E,E_{n-1}+1=(n-1)E\) adódik, így az utolsó két egyenletből \(\displaystyle E=1\). Ez a gondolatmenet azonban használja, hogy ezek véges értékek, így egy teljes megoldáshoz ezt még külön indokolni kell. (\(\displaystyle E=E_2=E_3=\dots=E_{n-1}=\infty\) esetén az egyenletek szintén teljesülnének!)
Statistics:
32 students sent a solution. 5 points: Baski Bence, Beke Csongor, Győrffi Ádám György, Hegedűs Dániel, Nagy Nándor, Osztényi József, Soós 314 Máté, Szabó 991 Kornél, Török Mátyás, Weisz Máté. 4 points: Bencsik Ádám, Csaplár Viktor, Fraknói Ádám, Füredi Erik Benjámin, Jánosik Áron, Sebestyén Pál Botond, Stomfai Gergely, Telek Zsigmond , Tóth 827 Balázs, Tóth Ábel, Várkonyi Zsombor, Zsigri Bálint. 3 points: 7 students. 2 points: 1 student. 1 point: 2 students.
Problems in Mathematics of KöMaL, April 2019