Táto úloha je voľným pokračovaním úloh Spravodlivá hra, Spravodlivá hra 2 a Spravodlivá hra 3.
Janko navrhol Mariánovi hru:
Janko má vrecko, v ktorom je 50 šedých guľôčok. Každá má iný odtieň. Marián nevie aké sú tie odtiene. Marián postupne náhodne vyťahuje guľôčky z vrecka, pozrie si ich odtieň a ukladá ich na stôl do radu podľa odtieňa. Bez ohľadu na to koľko ich vytiahne – či jednu jedinú alebo všetkých 50, tak pred každou hrou zaplatí Jankovi 1 pivo. Kedykoľvek sa môže rozhodnúť prestať ťahať. Ak je posledná vytiahnutá guľôčka najtmavšia zo všetkých 50, tak mu Janko zaplatí 5 pív.
Hra sa môže opakovať ale Janko po každej hre mení odtiene (takže Marián nevie pred začiatkom novej hry aký je najtmavší odtieň, ani aké sú ostatné).
Predpoklad: Aj keď sú obaja v princípe farboslepí, pre túto úlohu predpokladajme, že rozoznajú 50 odtieňov šedej.
Predpoklad: Pre túto úlohu predpokladajme, že Marián bude hrať ideálne.
Kto by celkovo vyhral a koľko by (v priemere) vyhral, ak by hrali túto hru 1 000 krát?
Riešenie
Ak bude Marián rozumný, tak vyhrá veľa pív.
Stratégia: Marián vytiahne 25 guľôčok. Ťahá ďalej, pokiaľ nevytiahne guľôčku tmavšiu ako je najtmavšia z prvých 25 guľôčok. Vtedy skončí.
Vysvetlenie: Ak rozdelíme náhodne guľôčky na dve polovice, tak najtmavšia je v druhej polovici s pravdepodobnosťou \(\frac{1}{2}\). Druhá najtmavšia je v prvej polovici s pravdepodobnosťou \(\frac{1}{2}\). To nastane naraz s pravdepodobnosťou \(\frac{1}{4}\), v takom prípade prvá guľôčka z druhej polovice, ktorá je tmavšia ako najtmavšia z prvej polovice musí byť celkovo najtmavšia. Preto sa zdá, že Marián pri tejto stratégii vyhrá v priemere každú štvrtú hru, t. j. má zisk +5 – 4 = 1 pivo. Za 1 000 hier je to 250 pív.
Ale reálne vyhrá pív 3x viac. Napríklad, vyhrá aj ak je najtmavšia guľôčka na 26. pozícii a vtedy je jedno akých je prvých 25 guľôčok. Alebo sú pred ňou v druhej polovici iba guľôčky svetlejšie ako tie v prvej polovici. Pre 50 guľôčok je úmorne zdĺhavé rozpísať všetky možnosti. Ja som to skúsil pre 2, 4, 6, 8, 10 guľôčok, zbadal som systém (vzor) a stvoril som vzorec pre párny počet guľôčok.
\(\frac{1}{i}+\sum\limits_{k=0}^{\frac{i}{2}-2} \left(\sum\limits_{j=0}^k \frac{i k! (i-j-2)!}{2 i! (k-j)!}\right)\), kde i je počet guľôčok.
Vzorec vracia pravdepodobnosť výhry. Otestoval som ho pre väčšie počty simuláciami Monte Carlo v Pythone a bolo to OK.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import random poc_sim = 100000 poc_gulocok = 50 poc_vyhier = 0 poc_piv = 0 for i in range(poc_sim): rs = random.sample(range(poc_gulocok), poc_gulocok) m = max(rs[:poc_gulocok//2]) if poc_gulocok -1 == next((x for x in rs[poc_gulocok//2:] if x > m), 0): poc_piv += 4 poc_vyhier += 1 else: poc_piv -= 1 print(f"Po {poc_sim} hrách: {poc_piv}pív, {poc_vyhier/poc_sim}.") |
A potom som zo vzorca urobil vzorček, toto zjednodušenie mi trvalo dlhšie ako vymyslieť pôvodný vzorec, ale stojí to za to:
\(\sum\limits_{k=\frac{i}{2}}^{i-1} \frac{1}{2k}\)
Pre 50 guľôčok je pravdepodobnosť výhry \(\frac{2179394248109401221881}{6198089008491993412800}\doteq 0,351624\), preto Marián z 1 000 hier vyhrá \( 1000\cdot 0,351624 \cdot 5\ – 1000 \doteq 758\) pív.
Čím je guľôčok viac, tak je pravdepodobnosť výhry nižšia, ale nikdy neklesne pod \(\frac{ln(2)}{2}\):
| 2 | 0,500000 |
| 4 | 0,416667 |
| 6 | 0,391667 |
| 8 | 0,379762 |
| 10 | 0,372817 |
| 20 | 0,359386 |
| 30 | 0,355046 |
| 40 | 0,352902 |
| 50 | 0,351624 |
| ∞ | ln(2)/2 ≈ 0,346574 |