Problem B. 4637. (May 2014)

B. 4637. Sir Bedevir will only enter in a tournament if he is certain that he will win with a probability of at least 1/2. In any combat of two knights, the probability of the victory of the parties are proportional to their fighting potentials. Bedevir's fighting potential is 1, and that of his \(\displaystyle n\)th opponent is \(\displaystyle \frac{1}{2^{n+1}-1}\). How many knights may have entered in the tournament if Bedevir, having carried out some careful calculations, also decided to enter?

(EMMV)

(5 pont)

Deadline expired on June 10, 2014.

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

Megoldás. Egy összecsapásban, ha a felek harcképessége \(\displaystyle a\) és \(\displaystyle b\), akkor az \(\displaystyle a\), illetve \(\displaystyle b\) harcképességű fél rendre \(\displaystyle \frac{a}{a+b}\), illetve \(\displaystyle \frac{b}{a+b}\) valószínűséggel győz.

Tehát Bedevir és az \(\displaystyle n\)-edik ellenfele közötti összecsapásban Bedevir győzelmének \(\displaystyle B_n\) valószínűsége:

\(\displaystyle B_n=\frac{1}{1+\frac{1}{2^{n+1}-1}}=\frac{2^{n+1}-1}{\big(2^{n+1}-1\big)+1} =\frac{2^{n+1}-1}{2^{n+1}}. \)

Becsüljük a tagokat alulról:

\(\displaystyle \frac{2^{n+1}-1}{2^{n+1}} =1-\frac{1}{2^{n+1}}>1-\frac{1}{2^{n+1}-1} =\frac{\big(2^{n+1}-1\big)-1}{2^{n+1}-1}=\)

\(\displaystyle = \frac{2^{n+1}-2}{2^{n+1}-1} =\frac{2(2^n-1)}{2^{n+1}-1}=2\cdot\frac{2^n-1}{2^{n+1}-1}.\)

Legyen Bedevir ellenfeleinek száma \(\displaystyle k\). Ekkor - mivel az összecsapások egymástól függetlenek - annak a valószínűsége, hogy Bedevir lesz a torna győztese:

\(\displaystyle P_k(B) =\prod_{n=1}^kB_n=\prod_{n=1}^k\frac{2^{n+1}-1}{2^{n+1}}>\prod_{n=1}^k 2\cdot\frac{2^n-1}{2^{n+1}-1}= 2^k\prod_{n=1}^k\frac{2^n-1}{2^{n+1}-1}=\)

\(\displaystyle =2^k\cdot\frac{2-1}{4-1}\cdot\frac{4-1}{8-1} \cdot\ldots\cdot\frac{2^{k-1}-1}{2^k-1} \cdot\frac{2^k-1}{2^{k+1}-1}= 2^k\cdot\frac{1}{2^{k+1}-1}>\frac{2^k}{2^{k+1}}=\frac12.\)

Tehát tetszőleges (bármilyen nagy) \(\displaystyle k\)-ra \(\displaystyle P_k(B)>\frac12\).

Mivel ez volt a feltétele Bedevir indulásának, ezért tetszőlegesen sok lovag jelentkezhetett a tornára (a jelentkezők száma Bedevirrel együtt \(\displaystyle k+1\)).

Seress Dániel (Debreceni Ref. Koll. Dóczy Gimn., 12. évf.)

Statistics:

65 students sent a solution.
5 points:	Ágoston Péter, Andó Angelika, Balogh Menyhért, Baran Zsuzsanna, Cseh Kristóf, Csépai András, Csitári Nóra, Di Giovanni Márk, Fekete Panna, Fonyó Viktória, Forrás Bence, Gáspár Attila, Győrfi-Bátori András, Kocsis Júlia, Kovács 246 Benedek, Kovács 972 Márton, Kuchár Zsolt, Kúsz Ágnes, Leitereg Miklós, Lőrinczy Zsófia Noémi, Maga Balázs, Nagy-György Pál, Nagy-György Zoltán, Olexó Gergely, Porupsánszki István, Schrettner Bálint, Schwarcz Tamás, Seress Dániel, Szakács Lili Kata, Szebellédi Márton, Török Tímea, Williams Kada.
4 points:	Bereczki Zoltán, Csernák Tamás, Kátay Tamás, Lajkó Kálmán, Nagy Gergely, Schefler Barna, Simkó Irén, Szőke Tamás, Telek Máté László, Tóth Ádám Bars.
3 points:	6 students.
2 points:	1 student.
1 point:	9 students.
0 point:	7 students.

Problems in Mathematics of KöMaL, May 2014