Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4430. feladat (2012. február)

B. 4430. Fej vagy írás játékot játszunk a következő módon. Mindegyik dobás előtt megteszünk egy tétet, ami legfeljebb akkora, amennyi pénzünk van, majd megtippeljük a dobás eredményét. Ha eltaláljuk, akkor visszakapjuk a tét kétszeresét, ha nem, akkor a tétet elveszítjük. Határozzuk meg azokat a k>1 értékeket, amelyekhez van olyan n egész szám és olyan stratégia, hogy legfeljebb n kört játszva legalább \frac{1}{k} valószínűséggel megszerezzük kezdeti pénzünk k-szorosát.

(5 pont)

A beküldési határidő 2012. március 12-én LEJÁRT.


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.


Statisztika:

21 dolgozat érkezett.
5 pontot kapott:Havasi 0 Márton, Janzer Olivér, Mester Márton, Strenner Péter, Viharos Andor, Zilahi Tamás.
4 pontot kapott:Kabos Eszter, Maga Balázs.
3 pontot kapott:1 versenyző.
2 pontot kapott:8 versenyző.
1 pontot kapott:2 versenyző.
0 pontot kapott:2 versenyző.

A KöMaL 2012. februári matematika feladatai