Problem B. 5476. (September 2025)
B. 5476. Each of Ali and Baba has a random number generator (RNG). Ali's RNG chooses one of numbers 1, 2, \(\displaystyle \ldots\), 100 with uniform distribution (each number is chosen with the same probability), and Baba's RNG chooses one of numbers 0, 1, 2, \(\displaystyle \ldots\), 100 with uniform distribution. Ali calculated the expected number of times he has to use his RNG to get a sum which is at least 101, and Baba calculated the expected number of times he has to use his RNG to get a sum which is at least 100. Whose number is bigger?
Proposed by: Attila Sztranyák, Budapest
(6 pont)
Deadline expired on October 10, 2025.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
53 students sent a solution. 6 points: 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 points: Bodó Rókus Dániel, Bodor Noémi, Tóth László Pál. 3 points: 1 student. 2 points: 1 student. 1 point: 1 student. 0 point: 28 students. Unfair, not evaluated: 1 solutions. Not shown because of missing birth date or parental permission: 1 solutions.
Problems in Mathematics of KöMaL, September 2025