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:

A B. 5476. feladat értékelése még nem fejeződött be.

A KöMaL 2025. szeptemberi matematika feladatai