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. 5018. feladat (2019. március)

B. 5018. A szultán birodalmának mind az 1024 matematikusát börtönbe zá­ratta. Mindegyikük csak a saját réztalléros érméjét tarthatta meg. A matematikusok tudják, hányan vannak, de semmiféle módon nem képesek kommunikálni egymással.

A szultán a születésnapján nagy kegyesen a következő játékot ajánlotta a matematikusoknak: az udvaron egyenként vagy 0-t, vagy 1-et mondanak. Ha a mondott számok összege 1, akkor szabadon bocsátja őket.

(A matematikusok nem adhatnak jelet egymásnak, nem tudják, hogy őket hányadiknak vitték ki, vagy hogy az előttük az udvaron lévők mit csináltak.)

Mekkora eséllyel szabadulhatnak ki a matematikusok?

(5 pont)

A beküldési határidő 2019. április 10-én LEJÁRT.


Megoldás. Általában legyen a matematikusok száma \(\displaystyle n\geq 1\). Azt mutatjuk meg, hogy a matematikusok akkor nyernek legnagyobb eséllyel, ha egymástól függetlenül \(\displaystyle \dfrac{1}{n}\) valószínűséggel mondanak az udvaron \(\displaystyle 1\)-et (és \(\displaystyle \dfrac{n-1}{n}\) valószínűséggel mondanak \(\displaystyle 0\)-t).

Minden matematikus mondjon \(\displaystyle p\) eséllyel \(\displaystyle 1\)-et az udvaron, és \(\displaystyle (1-p)\) eséllyel \(\displaystyle 0\)-t. Annak a valószínűsége, hogy pontosan 1 matematikus mond 1-et: \(\displaystyle P(1) = n p (1-p)^{n-1}\).

Ezt átalakítva, és felhasználva a számtani- és a mértani közepek közötti összefüggést, mely szerint
\(\displaystyle M((n-1)p;\underbrace{(1-p);...;(1-p)}_{(n-1) \text{~db}}) \leq S((n-1)p;\underbrace{(1-p);...;(1-p)}_{(n-1) \text{~db}})\):

\(\displaystyle P(1) = n p (1-p)^{n-1} = \dfrac{n}{n-1} \left( \sqrt[n]{(n-1)p (1-p)^{n-1}} \right)^n \leq\)

\(\displaystyle \leq\dfrac{n}{n-1} \left( \dfrac{(n-1)p +(n-1)(1-p)}{n} \right)^n = \dfrac{n}{n-1} \left( \dfrac{n-1}{n} \right)^n = \left( \dfrac{n-1}{n} \right)^{n-1}.\)

A számtani-mértani közép között pontosan akkor van egyenlőség, ha a tagok egyenlőek, azaz \(\displaystyle (n-1)p = (1-p)\), vagyis \(\displaystyle p=\dfrac{1}{n} \), és ekkor a szabadulás esélye \(\displaystyle \left(1- \dfrac{1}{n} \right)^{n-1}\).
(És ez az esély \(\displaystyle n \rightarrow \infty\) esetén is "jelentős", hiszen \(\displaystyle \left(1- \dfrac{1}{n} \right)^{n-1} \rightarrow \dfrac{1}{e} \).)

Mivel most \(\displaystyle p=\dfrac{1}{n} = \dfrac{1}{1024}\), ezért a matematikusok a cellájukban véges sok (legfeljebb 10 darab) pénzfeldobással el tudják dönteni, hogy mit mondjanak az udvaron.
Ha egy matematikusnak a cellájában az érméjét 10-szer feldobva mind a 10 dobása fej lett (ennek esélye pontosan \(\displaystyle \dfrac{1}{1024}\)), mondjon 1-t, különben mondjon 0-t.

Összefoglalva: a matematikusok optimális stratégia mellett \(\displaystyle \boxed{\: \left( \dfrac{1023}{1024} \right)^{1023} \approx 0,36806 \:}\) eséllyel szabadulhatnak ki (és ez ,,közel van" \(\displaystyle \dfrac{1}{e} \approx 0,36788\)-hoz).


Statisztika:

68 dolgozat érkezett.
5 pontot kapott:Baski Bence, Füredi Erik Benjámin, Győrffi Ádám György, Hegedűs Dániel, Jánosik Áron, Kerekes Boldizsár, Laki Anna, Nguyen Bich Diep, Sebestyén Pál Botond, Telek Zsigmond , Tóth 057 Bálint, Tóth 827 Balázs, Várkonyi Zsombor, Weisz Máté, Zsigri Bálint.
4 pontot kapott:Apagyi Dávid, Beke Csongor, Bukva Dávid, Fleiner Zsigmond, Fraknói Ádám, Hervay Bence, Kovács 129 Tamás, Kun Ágoston , Nagy 551 Levente, Nagy Nándor, Osztényi József, Sárvári Tibor, Soós 314 Máté, Tóth Ábel, Tóth-Rohonyi Iván.
3 pontot kapott:22 versenyző.
2 pontot kapott:2 versenyző.
1 pontot kapott:5 versenyző.
0 pontot kapott:9 versenyző.

A KöMaL 2019. márciusi matematika feladatai