Problem B. 5018. (March 2019)
B. 5018. The sultan imprisoned all the 1024 mathematicians of his empire. They were not allowed to keep any of their possessions except for a single copper coin each. The mathematicians know that there are 1024 of them, but they are not able to communicate with one another in any way.
On his birthday the sultan offered them the following game: they are taken to the prison yard one by one. Each of them may say either 0 or 1 when taken there. If the sum of the numbers they say is 1, then he will let them all go free.
(The mathematicians cannot signal to each other, they do not know how many others have been to the yard before them, or what those before them have done in the yard.)
What are the chances that they can get out of the prison?
(5 pont)
Deadline expired on April 10, 2019.
Sorry, the solution is available only in Hungarian. Google translation
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).
Statistics:
68 students sent a solution. 5 points: 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 points: 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 points: 22 students. 2 points: 2 students. 1 point: 5 students. 0 point: 9 students.
Problems in Mathematics of KöMaL, March 2019