 |
A B. 5476. feladat (2025. szeptember) |
B. 5476. Alinak és Babának is van egy-egy véletlenszám-generátora. Alié az \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle 100\) számok közül sorsol egyet egyenlő eséllyel, míg Babáé a \(\displaystyle 0\), \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle 100\) számok közül. (A sorsolások függetlenek egymástól.) Ali kiszámolta, hogy a saját gépét várhatóan hányszor kell használni ahhoz, hogy a sorsolt számok összege legalább \(\displaystyle 101\) legyen, míg Baba kiszámolta, hogy az ő gépét várhatóan hányszor kell használni ahhoz, hogy a sorsolt számok összege legalább 100 legyen. Melyikük várható értéke lett a nagyobb?
Javasolta: Sztranyák Attila (Budapest)
(6 pont)
A beküldési határidő 2025. október 10-én LEJÁRT.
100 helyett általánosan, \(\displaystyle n\)-re fogalmazzuk a megoldásainkat. Tehát Ali gépe az \(\displaystyle 1,2,\ldots,n\) számok közül sorsol és Ali legalább \(\displaystyle (n+1)\)-ig szeretne eljutni, míg Baba gépe a \(\displaystyle 0,1,2,\ldots,n\) közül sorsol, és legalább \(\displaystyle n\)-ig szeretne eljutni. A megoldásban a sorsológépek egy-egy használatára a ,,dobás'' szót is fogjuk használni (mintha egy \(\displaystyle n\) ill. \(\displaystyle n+1\) oldaú dobótestet használnának).
Első megoldás. Jelölje \(\displaystyle \alpha_k\), ill. \(\displaystyle \beta_k\) annak az esélyét, hogy Ali, ill. Baba a \(\displaystyle k\)-adik dobása után még nem jutott el a céljához (azaz még szükségük van a \(\displaystyle k+1\)-edik, esetleg azután még újabb dobásokra).
Ali egy \(\displaystyle k\) lépésből álló dobássorozata kölcsönösen egyértelműen megfeleltethető egy \(\displaystyle 0 < a_1 < a_2 < \ldots < a_k\) számsorozatnak, ahol \(\displaystyle a_i\) jelöli az első \(\displaystyle i\) dobásának összegét. Ha Ali még nem érte el a célját, akkor \(\displaystyle a_k \leq n\), tehát az \(\displaystyle (a_1,a_2,\ldots,a_k)\) szigorúan monoton növekvő sorozat \(\displaystyle \binom{n}{k}\)-féleképpen választható ki (az ismétlés nélküli kombináció képlete szerint). Ali első \(\displaystyle k\) dobása \(\displaystyle n^k\)-féle lehet, tehát annak az esélye, hogy \(\displaystyle k\) dobással még nem érte el a célját:
\(\displaystyle \alpha_k = \frac{\binom{n}{k}}{n^k}. \)
Baba egy \(\displaystyle k\) lépésből álló dobássorozata kölcsönösen egyértelműen megfeleltethető egy \(\displaystyle 0 \leq b_1 \leq b_2 \leq \ldots \leq b_k\) számsorozatnak, ahol \(\displaystyle b_i\) jelöli az első \(\displaystyle i\) dobásának összegét. Ha Baba \(\displaystyle k\) dobásból még nem érte el a célját, akkor \(\displaystyle b_k < n\), tehát a \(\displaystyle (b_1,b_2,\ldots,b_k)\) monoton növekvő sorozat \(\displaystyle \binom{n+k-1}{k}\)-féleképpen választható ki. (Az ismétléses kombináció képletét használjuk, az \(\displaystyle n\)-elemű \(\displaystyle \{ 0,1,\ldots,n-1 \}\) halmazból választunk \(\displaystyle k\) elemet).
Baba első \(\displaystyle k\) dobása \(\displaystyle (n+1)^k\)-féle lehet, tehát annak az esélye, hogy \(\displaystyle k\) dobással még nem érte el a célját:
\(\displaystyle \beta_k = \frac{\binom{n+k}{k}}{(n+1)^k}. \)
Ismert, hogy ha egy \(\displaystyle X\) valószínűségi változó csak nemnegatív egész értékeket vehet fel, akkor a várható értéke megkapható úgy, hogy összeadjuk minden \(\displaystyle k\) nemnegatív egész számra annak valószínűségét, hogy \(\displaystyle X > k\). Képlettel kifejezve:
\(\displaystyle \mathbb{E}(X) = \sum_{k=0}^{\infty} P (X > k). \)
Ezt a kiszámítási módot úgy érdemes felfogni, hogy minden \(\displaystyle k\) nemnegatív egészre megnézzük, hogy mekkora eséllyel lesz szükség az \(\displaystyle (k+1)\)-edik dobásra (avagy mekkora az esélye annak, hogy a \(\displaystyle (k+1)\)-edik dobás is hozzájárul 1-gyel a dobások számához), és ezeket adjuk össze. Az \(\displaystyle k\)-adik dobásra éppen akkor van szükség, ha \(\displaystyle X > k\).
Ezt felhasználva Ali dobásai számának várható értéke:
\(\displaystyle \sum_{k=0}^{\infty} \alpha_k = \sum_{k=0}^{\infty} \binom{n}{k} \frac{1}{n^k} = \sum_{k=0}^n \binom{n}{k} \frac{1}{n^k} = \bigg(1+\frac1n\bigg)^n \)
Az utolsó egyenlőségnél a binomiális tételt használtuk.
Baba dobásai számának várható értéke pedig:
\(\displaystyle \sum_{k=0}^{\infty} \beta_k = \sum_{k=0}^\infty \binom{n+k-1}{k}\frac{1}{(n+1)^k} = \left(\dfrac{1}{1-\dfrac1{n+1}}\right)^n = \bigg(1+\frac1n\bigg)^n \)
Az utolsó előtti egyenlőségnél az alábbi közismert (a hatványsorok világában alapvető, \(\displaystyle |x| < 1\) esetén mindig teljesülő) azonosságokat használtuk:
\(\displaystyle \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k = \left( \sum_{k=0}^{\infty} x^k \right)^n \quad \text{ és } \quad \sum_{n=0}^{\infty} x^k = \frac1{1-x} \)
Tehát a két vizsgált várható érték megegyezik.
Második megoldás. Jelölje \(\displaystyle A_k\) ill. \(\displaystyle B_k\), hogy átlagosan (várható értékben) hány dobásra van még szüksége Alinak ill. Babának a célja eléréséhez, ha az eddigi dobásainak összege \(\displaystyle k\).
Ali esetében \(\displaystyle A_k = 0\), ha \(\displaystyle k \geq n+1\), továbbá minden \(\displaystyle k \in \{0,1,\ldots,n\}\) esetén
\(\displaystyle A_k = 1 + \frac1{n} \left( A_{k+1} + A_{k+2} \ldots + A_{k+n} \right) = 1 + \frac1{n} \left( A_{k+1} + A_{k+2} \ldots + A_{n} \right), \)
hiszen ha Ali eddigi dobásösszege \(\displaystyle k\), akkor ez egy újabb dobással megnő \(\displaystyle k+1, k+2, \ldots, k+n\) valamelyikére – mindegyikre egyenlő, \(\displaystyle \frac1{n}\) eséllyel. Ha pedig az így elért új összeg \(\displaystyle \ell\), akkor még átlagosan \(\displaystyle A_\ell\) lépésre van szüksége a célja eléréséhez.
Az is világos, hogy \(\displaystyle A_n = 1\) (hiszen ilyenkor bármit is dob Ali, célt ér). Tovább minden \(\displaystyle k \in \{0,1,\ldots,n-1 \}\) esetén \(\displaystyle A_k - A_{k+1} = \frac1{n} A_{k+1}\), azaz \(\displaystyle A_k = \frac{n+1}{n} A_{k+1}\)
Következésképpen \(\displaystyle A_k = \left( \frac{n+1}{n} \right)^{n-k}\) (minden \(\displaystyle k \in \{0,1,\ldots,n \}\) esetén, tehát Alinak a teljes játék során átlagosan (várható értékben) \(\displaystyle A_0 = \left( \frac{n+1}{n} \right)^{n}\) alkalommal kell használja a gépét.
Baba esetében \(\displaystyle B_k = 0\), ha \(\displaystyle k \geq 100\) és minden \(\displaystyle k \in \{0,1,\ldots,n-1 \}\) esetén
\(\displaystyle B_k = 1 + \frac1{n+1} \left( b_{k} + b_{k+1} \ldots + b_{k+n} \right) = 1 + \frac1{n+1} \left( b_{k} + b_{k+1} \ldots + b_{n} \right), \)
hiszen ha Baba eddigi dobásainak összege \(\displaystyle k\), akkor egy újabb dobással együtt az összeg lehet \(\displaystyle k, k+1, k+2, \ldots, k+n\), mindegyik egyenlő, \(\displaystyle \frac1{n+1}\) eséllyel. Ha az új összeg \(\displaystyle \ell\), akkor még átlagosan \(\displaystyle B_\ell\) lépésre van szüksége a célja eléréséhez.
Egyrészt a fenti formula szerint \(\displaystyle B_{n-1} = 1 + \frac1{n+1} B_{n-1}\), azaz \(\displaystyle B_{n-1} = \frac{n+1}{n}\), másrészt minden \(\displaystyle k \in \{0,1,\ldots,n-2 \}\) esetén \(\displaystyle B_k - B_{k+1} = \frac1{ n+1} B_{k}\), amiből \(\displaystyle B_k = \frac{n+1}{n} B_{k+1}\).
Következésképpen \(\displaystyle B_k = \left( \frac{n+1}{n} \right)^{n-1-k} B_{n-1} = \left( \frac{n+1}{n} \right)^{n-k} \) (minden \(\displaystyle k \in \{0,1,\ldots,n-1 \}\) esetén, tehát Baba a teljes játék során átlagosan (várható értékben) \(\displaystyle B_0 = \left( \frac{n+1}{n} \right)^{n}\) alkalommal kell használja a gépét – ez megegyezik az Ali esetében kapott értékkel.
Statisztika:
53 dolgozat érkezett. 6 pontot kapott: Ali Richárd, Bodor Ádám, Budai Máté, Diaconescu Tashi, Ercse Ferenc, Fodor Barna, Gyenes Károly, Holló Martin, Körmöndi Márk, Li Mingdao, Pázmándi József Áron, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Tulkán Dávid. 5 pontot kapott: Bodó Rókus Dániel, Bodor Noémi, Tóth László Pál. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 27 versenyző. Nem versenyszerű: 1 dolgozat. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 2 dolgozat.
A KöMaL 2025. szeptemberi matematika feladatai