Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4430. (February 2012)

B. 4430. We play the following game of tossing a coin: We make a bet before each toss. The bet may be at most as large as all the money we have. Then we make a guess on the result. If our guess is right, we will receive the double of the bet, otherwise we will lose it. Determine those values of k>1 for which there exists an integer n with a strategy such that the probability of receiving k times our initial amount of money in at most n games is at least \frac{1}{k}.

(5 pont)

Deadline expired on March 12, 2012.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Engedjük meg, hogy 0 tétet is megtehetünk. Ekkor egy olyan stratégia, melyben legfeljebb \(\displaystyle n\) kört játszunk, tekinthető olyannak, amelyben pontosan \(\displaystyle n\) kört játszunk, és egy olyan stratégia, amelyben pontosan \(\displaystyle m\) kört játszunk, minden \(\displaystyle n\ge m\) esetén tekinthető olyannak, amelyben pontosan \(\displaystyle n\) kört játszunk. Ha egy adott pillanatban \(\displaystyle K\) mennyiségű pénzünk van, és \(\displaystyle T\le K\) tétet teszünk meg, akkor a dobás után \(\displaystyle 1/2\) valószínűséggel \(\displaystyle K+T\), \(\displaystyle 1/2\) valószínűséggel pedig \(\displaystyle K-T\) pénzünk lesz, tehát várhatóan a dobás után is

\(\displaystyle \frac{1}{2}\cdot(K+T)+\frac{1}{2}\cdot(K-T)=K\)

mennyiségű pénzünk lesz. Várhatóan tehát mindig ugyanannyi pénzünk lesz, mint kezdetben. Ezért \(\displaystyle 1/k\)-nál nagyobb valószínűséggel nem szerezhetjük meg kezdeti pénzünk \(\displaystyle k\)-szorosát, ha pedig egy adott, pontosan \(\displaystyle n\) körből álló stratégiával meg tudjuk szerezni \(\displaystyle 1/k\) valószínűséggel kezdeti pénzünk \(\displaystyle k\)-szorosát, akkor annál a stratégiánál \(\displaystyle (k-1)/k\) valószínűséggel minden pénzünket elveszítjük. A kérdés tehát az, hogy mely \(\displaystyle n,k\) értékekre van olyan \(\displaystyle S_{n,k}\) stratégia, mely stratégia pontosan \(\displaystyle n\) kör lejátszását kívánja meg, és azt alkalmazva \(\displaystyle 1/k\) valószínűséggel kezdeti pénzünknek pontosan \(\displaystyle k\)-szorosát szerezzük meg, a maradék \(\displaystyle (k-1)/k\) valószínűséggel pedig minden pénzünket elveszítjük.

Egy ilyen stratégiánál minden esemény valószínűsége \(\displaystyle 1/2^n\)-nek egész számú többszöröse, ami azt jelenti, hogy \(\displaystyle k\) értéke (a triviális \(\displaystyle k=1\) esetet is megengedve) \(\displaystyle 2^n/t\) alakú kell legyen, ahol \(\displaystyle t\le 2^n\) pozitív egész szám. A továbbiakban megmutatjuk, hogy minden \(\displaystyle n\) pozitív egészre és \(\displaystyle 0<t\le 2^n\) egész számra van \(\displaystyle S_{n,k}\) stratégia, ahol \(\displaystyle k=2^n/t\). Ehhez feltesszük, hogy kezdeti \(\displaystyle K\) pénzmennyiségünk tetszőlegesen osztható (azt mindenképpen fel kell tennünk, hogy \(\displaystyle t/(2^n,t)\)-vel osztható, máskülönben annak pontosan \(\displaystyle k\)-szorosa nem értelmezhető mennyiség).

Ezt \(\displaystyle n\) szerinti teljes indukcióval végezzük. Ha \(\displaystyle n=1\), akkor az állítás nyilvánvaló: az \(\displaystyle S_{1,1}\) stratégia abból áll, hogy 1 kört játszunk úgy, hogy 0 tétet teszünk meg. Legyen tehát \(\displaystyle n>1\), és tegyük fel, hogy kisebb \(\displaystyle n\) értékekre már az állítást igazoltuk. Ha \(\displaystyle t=2s\) páros szám, ahol \(\displaystyle 0<s\le 2^{n-1}\), akkor \(\displaystyle k=2^n/t=2^{n-1}/s\), ekkor tehát kezdeti megjegyzésünk szerint \(\displaystyle S_{n,k}=S_{n-1,k}\) megfelelő (az \(\displaystyle n\)-edik körben 0 tétet teszünk meg). Ha \(\displaystyle t=1\), akkor az \(\displaystyle S_{n,2^n}\) stratégia álljon abból, hogy minden egyes körben az összes pénzünket feltesszük; ez nyilván jó lesz. Végül ha \(\displaystyle t=2s+1\) páratlan szám, ahol \(\displaystyle 1\le s<2^{n-1}\), akkor stratégiánk legyen a következő. Az első körben tegyük meg pénzünk \(\displaystyle t\)-ed részét. Ha nyerünk, akkor a hátralévő \(\displaystyle n-1\) körre alkalmazzuk az \(\displaystyle S_{n-1,k_1}\) stratégiát, ahol \(\displaystyle k_1=2^{n-1}/(s+1)\), ha pedig veszítünk, akkor a hátralévő \(\displaystyle n-1\) körre alkalmazzuk az \(\displaystyle S_{n-1,k_2}\) stratégiát, ahol \(\displaystyle k_2=2^{n-1}/s\). Így az első kör után \(\displaystyle 1/2\) valószínűséggel \(\displaystyle (t+1)K/t\), \(\displaystyle 1/2\) valószínűséggel pedig \(\displaystyle (t-1)K/t\) pénzünk lesz. Feltéve az első esetet, az indukciós feltevés szerint a játék végére \(\displaystyle 1/k_1\) valószínűséggel szerzünk

\(\displaystyle k_1\cdot\frac{(t+1)K}{t}= \frac{2^{n-1}}{s+1}\cdot \frac{(2s+2)K}{t}= \frac{2^nK}{t}=k\cdot K\)

pénzmennyiséget (vagy mindent elveszítünk), a második esetet feltételezve a játék végére \(\displaystyle 1/k_2\) valószínűséggel szerzünk

\(\displaystyle k_2\cdot\frac{(t-1)K}{t}= \frac{2^{n-1}}{s}\cdot \frac{(2s)K}{t}= \frac{2^nK}{t}=k\cdot K\)

pénzmennyiséget. Ennél a stratégiánál tehát kezdeti \(\displaystyle K\) pénzünk \(\displaystyle k\)-szorosát éppen

\(\displaystyle \frac{1}{2}\cdot\frac{1}{k_1}+\frac{1}{2}\cdot\frac{1}{k_2}= \frac{1}{2}\cdot\frac{s+1}{2^{n-1}}+\frac{1}{2}\cdot\frac{s}{2^{n-1}}= \frac{1}{2}\cdot\frac{2s+1}{2^{n-1}}=\frac{t}{2^n}=\frac{1}{k}\)

valószínűséggel fogjuk megszerezni.


Statistics:

21 students sent a solution.
5 points:Havasi 0 Márton, Janzer Olivér, Mester Márton, Strenner Péter, Viharos Andor, Zilahi Tamás.
4 points:Kabos Eszter, Maga Balázs.
3 points:1 student.
2 points:8 students.
1 point:2 students.
0 point:2 students.

Problems in Mathematics of KöMaL, February 2012