Príspevky do našej novej súťaže sa nejako nehrnú, tak som sa rozhodol Vás trochu inšpirovať nasledovnou úlohou:Dvaja hráči sa dohodli na takýchto pravidlách: Na začiatku si každý hráč zvolí trojicu po sebe idúcich výsledkov hodu mincou, t.j. jednu z možností HHH, HHZ, HZH, HZZ, ZHH, ZHZ, ZZH a ZZZ, kde H znamená hlava a Z znamená znak. Vyhráva ten hráč, ktorého trojica sa pri hádzaní mincou vyskytne ako prvá. Napríklad ak si prvý hráč vyberie trojicu HZZ, druhý hráč trojicu ZZH a na minci padne postupne ZHZHHZHHHZZ, tak vyhráva prvý hráč, pretože trojica HZZ po sebe idúcich výsledkov sa pri hádzaní objavila skôr ako trojica ZZH. Hráč, ktorý si vyberá svoju trojicu ako druhý v poradí, si nemôže zvoliť rovnakú trojicu ako prvý hráč, avšak vie čo si prvý hráč vybral a tomu môže svoju voľbu trojice prispôsobiť. Otázka znie: Je táto hra spravodlivá pre oboch hráčov? Ak nie, ktorý hráč má výhodu?
Dodatok 21.11.: Rasťo už tento problém správne intuitívne odhadol a načrtol riešenie. Aby sme si vyjasnili aj detaily, nakreslil som nasledovný diagram (zodpovedajúci modelu situácie markovovským reťazcom):
Ako je možné z tohoto obrázka vyčítať, ktorú trojicu si má zvoliť druhý hráč v závislosti od toho, ktorú trojicu si zvolí prvý hráč?
14 komentárov:
zjednodusim si to na postupnost dvoch, tj voli si zz,zh,hz,hh
prvy ma v podstate 2 moznosti zz a zh (zvysok je symetricky) oznacme p-pravdepodobnost ze vyhra prvy
druhy ma 3 moznosti (musi dat inu)
ak da pravy opak tj zz->hh resp zh->hz tak z dovodu symetrie je p=1/2
tvdim, ze ak 1. da zz a 2. hz tak p=1/4 v skutocnosti si staci rozpisat moznosti prvych dvoch hodov a je to aj najlepsia odpoved druheho
ak da 1. zh a 2. hh => p=3/4
ine odpovede vedu na p=1/2
teda nashovo equlibrium: 1. da zh (resp. hz) 2. da zz, alebo hz (hh, zh) a p=1/2 teda hra je symetricka
tato uloha sa mi velmi paci, ale omylom som tukol v ratingu na 1* namiesto 5* :-(
Braňo: Fajn; ak uvažujeme stávku na dvojice, tak je to skutočne spravodlivá hra. Ale to ešte nie je dôkaz, že je tá hra spravodlivá aj pre stávku na trojice :-)
S tými hviezdičkami si nerob starosti; skús ešte raz kliknúť a ak sa Ti tým nepodarí to hodnotenie zmeniť, tak to nechaj tak. Aj tak veľmi málo ľudí kliká na tie hviezdičky (odhadom len tak každý päťdesiaty až stý, čo si môj prípsevok prečíta) a spoľahlivé uzávery o popularite článkov sa z toho robiť nedajú.
Z Pravdepodobnosti a štatisktiky som mal E, takže ma berte s rezervou.
Môj odhad je taký, že druhý hráč má výhodu. Nech si prvý hráč zvolí akúkoľvek trojicu ABC, stratégiou druhého by mohlo byť zvoliť si XAB.
Teda keď padne AB, možno očakávať, že s pravdepodobnosťou 0.5 tomu predchádzalo X a teda vyhráva druhý hráč, hra sa končí. Ak však nepadlo XAB, pokračuje sa. S pravdepodobnosťou 0.5 padne teraz C.
Takže výhra druhého akoby závisela vzhľadom na sekvenciu AB iba od jedného predchádzajúceho hodu (0.5), kým na výhru prvého nesmie pred sekvenciou AB padnúť X a musí po nej padnúť C (0.25). Teda šance druhého na výhru pri tejto stratégii sú 2:1.
Trochu nepekne vysvetlené, ale je to nejak tak, nie? Ak nie, tak idem za doc. Jankovou, nech mi vyškrtne to E a spravím si skúšku ešte raz:-)
rasťo: Nó, to znie celkom rozumne, aj keď tomu úplne na nerozumiem (ale chyba bude asi vo mne; už ledva držím otvorené oči). Skús napísať tabuľku: Ak prvý staví na HHH, tak druhý staví na ZHH a z toho a toho dôvodu s väčšou pravdepodobnosťou vyhrá druhý, ak prvý staví na ZHH, tak druhý staví na ...
Inak zaregistroval som Tvoj nový blog; super! Všimol som si, že si si tam nakopíroval už nejaké zaujímavé staršie príspevky (keď budem mať viac času, tak si to prejdem celé). Pokúsim sa Ti urobiť tu trochu reklamu, aby si ľudia ten Tvoj blog všimli.
Dobre, skúsim názornejšie:
Prvý si vyberie napríklad ZHH.
Druhý si teda vyberie niečo, čo končí ZH. Napríklad ZZH.
Po určitom počte hodov sa môžu vyskytnúť takéto situácie (pre úplnosť sú v tabuľke niektoré hody navyše - posledný hod v prvom a treťom riadku):
ZZHZ
HZHZ
ZZHH
HZHH
Boldom sú znázornené výherné trojice druhého a italics prvého. Vidíme, že druhý vyhráva v dvoch prípadoch, prvý v jednom - jednu jeho šancu na výhru mu totiž druhý "tesne uchmatol" v treťom riadku tabuľky.
Ďakujem za reklamu na môj blog. Úplne ma to dojalo a potešilo:-) Naozaj vďaka za to. Moja pôvodná stránka vznikla ako povinná domáca úloha. Na blogspot som prešiel kvôli väčšej interaktivite a funkčnosti. Tak ešte raz vďaka za povzbudenie:-)
rasťo: Uvažuješ veľmi rozumne, ale napríklad ak by si niekedy chcel učiť, musel by si sa vyjadrovať trochu presnejšie a úplnejšie (aby to pochopil naozaj každý).
Napríklad vo všeobecnosti druhému nezaručuje výhodu vsadiť na hocičo, čo končí na počiatočnú dvojicu z trojice prvého. Napríklad ak prvý vsadí na ZHZ, a druhý na HZH, tak sú šance fifty-fifty. Na stopercentne presvedčivé riešenie by sa tiež zišlo rozobrať situáciu na úplnom začiatku hádzania (kde nemôžeš nič "predradiť").
Ten obrázok sa mi páči :-)
V krúžkoch sú znázornené všetky možné trojice (striedajú sa dva stavy H a Z, teda rôznych trojíc by malo byť 2^3 = 8, čo sedí). Trojicu určujú vždy posledné tri hody v sekvencii hodov. Preto sa trojice nestriedajú len tak "od buka do buka", ale sa vyskytujú v nejakých následnostiach. Všetky možné následnosti zobrazuje obrázok. Z každej trojice vychádzajú dve šípky ukazujúce na možné nasledujúce trojice, a vchádzajú dve šípky z predchádzajúcich trojíc.
Červená šípka znamená, že padol znak, modrá, že hlava.
No ale ako to celé teda interpretovať? Výhodné je, ak "moja šípka smeruje k súperovi, a jeho nesmeruje ku mne a ak žiadna moja šípka nesmeruje naspäť ku mne".
Ak prvý zvolí ZZZ alebo ZZH (HHH alebo HHZ), treba si vybrať HZZ (ZHH) a je to skoro vyhraté (môže sa stať, že na začiatku by hneď prvé tri hody boli ZZZ, akonáhle však už padne nejaké H, víťazstvo nutne čaká na druhého.)
Ak si prvý zvolí ZHH (HZZ), oplatí sa zvoliť HZH (ZHZ), aj keď tu mi už nie je jasné, či je to výhodnejšie ako ZZH (HHZ).
Keď prvý zvolí HZH (ZHZ), druhému sa oplatí HHZ (ZZH).
Hm, ale to nie je nijaký dôkaz. Takže, ako to teda má byť presne (tak presne, aby sa za to dalo napísať Q.E.D.:-)?
A ešte, čo sa týka učenia... najhoršie na tom je, že veciam poriadne nerozumiem (a najmä v kombinatorike:-(. Jedna vec je niečo intuitívne odhadnúť, poprípade vyriešiť príklad, druhá vec je naozaj tomu rozumieť a sprostredkovať pochopenie aj iným. Byť dobrým učiteľom je asi riadne ťažké, a hlavne stále neviem, ako sa tomuto majtrovstvu naučiť...
Rasťo: Vzťah diagramu k nášmu problému môžeme interpretovať nasledovne: Hodíme prvé tri hody, čím sa determinuje náš počiatočný stav (krúžok) v diagrame. Všimneme si, že každá trojica má rovnakú pravdepodobnosť, čiže každý počiatočný stav nastáva s rovnakou pravdepodobnosťou 1/8. Po ďalších hodoch prechádzame medzi jednotlivými stavmi na základe toho, aký výsledok nám padne na minci (ako si to popísal), t.j. každú z dvojice východzích ciest volíme s pravdepodobnosťou 1/2. Vyhráva samozrejme ten hráč, ktorého trojicu (t.j. príslušný stav) navštívime pri tejto náhodnej prechádzke ako prvý. Tiež si treba uvedomiť (nie je asi potrebné to dokazovať formálne), že s istotou skôr či neskôr dosiahneme niektorý z týchto zvolených dvoch stavov.
Ak prvý staví na HHH, tak druhý staví na ZHH. V tomto prípade musí vyhrať druhý vždy s vínimkou prípade, že hneď v prvých troch hodoch padne HHH, lebo do HHH existuje len cesta cez stav ZHH. Pravdepodobnosť výhry druhého je teda až 7/8.
Ak prvý staví na HHZ, tak druhý staví tiež na ZHH. Podobne ako v predchádzajúcom prípade, môže prvý vyhrať len ak budú prvé tri hody HHZ, alebo HHH; inak vyhrá druhý. Tu je teda pravdepodobnosť výhry druhého 3/4.
Ak prvý staví na ZHH, druhý staví na ZZH. V tomto prípade zaručene vyhrá druhý vtedy, ak počiatočné hody dopadnú (napríklad) ktorýmkoľvek z nasledovných prípadov: ZZH, ZZZ, HZZ, ZHZZ, HHZZ, HZHZZ. Pravdepodobnosť, že začiatok hádzania bude niektorá z týchto postupností je väčšia ako 1/2, čiže druhý má nutne výhodu.
Ak prvý staví na HZH, tak druhý staví na HHZ. V tomto prípade určite vyhrá druhý ak na začiatku padne ktorákoľvek z postupností: HHZ, HHH, ZHH, ZZHH, ZZZHH, HZZHH, ZHZZHH, čoho pravdepodobnosť je opäť väčšia ako 1/2.
Analogicky môžeme postupovať pre ostatné štyri trojice počiatočných hodov, kde znaky zameníme s hlavami.
QED.
Nevypočítali sme presne s akou pravdepodobnosťou vyhrá druhý hráč v prípadoch 3 a 4; dostať konkrétnu pravdepodobnosť výhry je už trochu ťažšie. Každopádne ukázali sme, že tá pravdepodobnosť je viac ako 1/2.
Tato uloha ma potesila za posledny tyzden uz treti krat. Po prvy raz, ked som ju videla riesenu v knihe pomocou vytvarajucich funkcii (minuly stvrtok). Po druhy raz, ked mi presla konkurzom do zadani korespondaku pre desatrocne deti (v sobotu). A po treti krat teraz, ked som ju nasla na blogu (dnes). A dovtedy som o nej nikdy nepocula, hoci sa uz s pravdepodobnostou par rokov hram.
kacka: Keď ma napadne pekná a jednoduchá úloha, tak väčšinou neskôr zistím, že sa už v nejakej forme niekde vyskytla. To je, zdá sa, aj prípad tejto úlohy. V akej knihe sa to vlastne rieši pomocou vytvárajúcich funkcií?
Mne sa hlavne paci, ze ked niekde nieco nacitam, tak potom to nasledne identifikujem hned na viacerych miestach.
Je to v knihe Concrete Mathematics autorov Graham, Knut, Patashnik, kapitola 8, Discrete probability, cast 8.4 Flipping coins, v originali str.408.
Citali sme tuto knihu na Zimnej skole (matematika pre IKT), tuto cast referoval Buggo (doktorand u Vas na informatike).
Ta kniha ja znama, ale bohuzial ju nemam. Inak buggo sedi tuto par kancelarii vedla mna; dokonca som mu robil oponenta na pisomnu pracu k dizertacnej skuske :)
No svet je vcelku maly.
Knihu mozem na par dni pozicat, prilezitostne poslem po Ajke.
Zverejnenie komentára