Ako hrať proti telepatovi

Koncom minulého týždňa mi poslal peknú úlohu môj bývalý študent Lukáš Poláček. Ďakujem(e)! Pre náš blog ju formulujem nasledovne:

Hráči A a B budú hrať takúto hru: Obaja pošlú rozhodcovi obálku s lístkom, na ktorom je číslo od 1 po 16; je len na ich vlastnom rozhodnutí akým spôsobom toto číslo hráči zvolia. Po obdržaní oboch obálok ich rozhodca otvorí a ak sa budú čísla na lístkoch líšiť práve o 1, tak vyhráva hráč A, inak vyhráva hráč B. Problém je v tom, že hráč B je telepat a čokoľvek vie hráč A, vie ihneď aj hráč B. Hráč A sa preto rozhodol, že bude svoje číslo voliť nasledovne: Najprv si pripraví viacero lístkov, na ktoré napíše čísla v rozmedzí od 1 do 16. Z týchto lístkov potom náhodne vyberie jeden, bez pozretia ho vloží do obálky a pošle ho rozhodcovi. Poraďte hráčovi A koľko lístkov si má pripraviť a aké čísla má na ne napísať, aby maximalizoval svoju šancu na výhru.

(Pochopiteľne, ilustračný obrázok vľavo hore nemusí korešpondovať s najlepším riešením.)

Päť klubov

Predchádzajúcu úlohu sme zatiaľ vyriešili pre n ktoré je nanajvýš štyri a keďže všeobecné riešenie sa zdá byť pomerne komplikované, pokúsme sa rozlúsknuť aspoň špeciálny prípad n=5. Nasledovnú úlohu formulujem bez použitia pravdepodobnosti, len pomocou elementárnych pojmov.

V istom meste existuje päť klubov: literárny, golfový, šachový, rybársky a bowlingový. Tieto kluby majú spolu m členov, pričom každý z týchto klubov má presne m/2 členov (vieme, že m je párne, ale inak o m nevieme nič). Dvojice klubov pravidelne organizujú spoločné stretnutia, na ktoré pozvú všetkých tých ľudí, ktorí sú členmi súčasne oboch klubov. Napríklad býva stretnutie ľudí, ktorí sú súčasne členmi rybárskeho aj šachového klubu, býva tiež stretnutie ľudí, ktorí sú súčasne členmi literárneho aj bowlingového klubu a tak ďalej (spolu 10 druhov stretnutí). Každého z týchto stretnutí sa vždy zúčastnia všetci pozvaní hostia. Tvrdíme, že na niektoré stretnutie určite príde aspoň p percent z daných m ľudí. Aké je maximálne p, označme ho p₅, pre ktoré je toto tvrdenie zaručene pravdivé?

Z komentáru k predchádzajúcej úlohe vieme, že p₅ je aspoň 15% a nie je ťažké sa presvedčiť, že p₅ je najviac 25%. (Viete prečo?) Kto nájde hodnotu p₅ presne (a presvedčivo túto hodnotu zdôvodní), má u mňa čokoládu. Nie je to vôbec až také ľahké, ale ani nemožné.

Samé polovice

Nech n>=2 je prirodzené číslo. Nájdite najväčšie číslo p_n s nasledovnou vlastnosťou: Ak každá z udalostí A₁,...,A_n má pravdepodobnosť 1/2, potom existujú rôzne indexy i,j také, že pravdepodobnosť súčasného nastatia udalostí A_i a A_j je aspoň p_n.

Formulujme túto úlohu aj bez použitia pravdepodobnosti (hoci máličko menej všeobecne): Pre n>=2 nájdite najväčšie také číslo p_n, že ak zjednotenie n množín plochy 1/2 má plochu nanajvýš 1, tak plocha prieniku niektorej dvojice z týchto množín je aspoň p_n.

Je zrejmé, že p₂=0 a z ilustračného obrázku sa zdá, že p₃=1/6. Viete to dokázať? Viete nájsť hodnotu p_n pre niektoré (alebo aj všetky) čísla n>=4?

Poznámka 23.10.: Dnes ráno ma napadlo pomerne jednoduché trikové riešenie využívajúce niektoré základné poznatky z pravdepodobnosti. Hodnota p_n je prekvapivo jednoduchou funkciou počtu udalostí n, hoci výsledný vzorček je trochu odlišný pre párne a pre nepárne n.

Beta verzia "Zbierky úloh z pravdepodobnosti" je live

Ešte pred dokončením našej zbierky úloh z pravdepodobnosti sme sa rozhodli, že urobíme malý experiment: jej odľahčenú internetovú verziu. Zatiaľ sme uverejnili zadania prvých štyroch podkapitol (asi 50 úloh; celkovo ich je v zbierke vyše 400) a budeme čakať, čo na to študenti. Využijú možnosť pýtať sa nás na detaily zadaní a diskutovať o riešeniach medzi sebou? Uvidíme a podľa toho sa zariadime v budúcnosti.

Každopádne, ak máte chvíľku čas, mohli by ste sa na našu zbierku pozrieť aj Vy a prípadne nám poradiť, čo by sa na nej podľa Vás dalo zlepšiť. Budeme veľmi povďační!

Ilustračný obrázok vľavo je môj návrh na obálku tlačenej verzie zbierky. Ak k nemu máte výhrady, sem s nimi. Ešte stále je čas všetko zmeniť :-)

PS: Ak by ste aj Vy chceli vyriešiť nejakú úlohu v zbierke, ale nepoznáte pravdepodobnostnú formalizáciu z našich prednášok, vyskúšajte napríklad takú úlohu 55. Ďalšie neformálne a nie celkom triviálne úlohy prídu neskôr.

Kombinatorická identita

Už takmer 12 hodín bez väčšej prestávky pracujem na zbierke príkladov z pravdepodobnosti. (Neverili by ste, koľko je s jej napísaním roboty; ale čím ďalej, tým viac sa ma zmocňuje pocit, že keď bude naša zbierka na svete, tak z nej budeme mať radosť.)

Práve som písal riešenie jedného príkladu, v ktorom som použil nasledovnú kombinatorickú identitu:


Hľadím na ňu už asi dvadsať minút a nenapadá ma, ako by som ju dokázal. Vedeli by ste mi pomôcť?

Ďalšia zapeklitá úloha z pravdepodobnosti

Už sa teším na obdobie, keď odovzdáme do tlače našu zbierku úloh z teórie pravdepodobnosti a budem sa môcť rozpísať napríklad o nedávnej návšteve "Univerza" v Brémach, alebo o množstve zaujímavých nových odkazov. Dovtedy však zo mňa nedostanete nič viac, ako len ďalšiu zapeklitú úlohu z pravdepodobnosti. Tentokrát je podľa mňa celkom pozoruhodná a ak sa ju niekomu podarí do týždňa vyriešiť nejakým jednoduchým trikom bez použitia náhodných premenných, má u mňa dve odmeny: jeho meno sa objaví v našej zbierke a darujem mu jeden exemplár zbierky aj s podpismi autorov :-)

Dokážte, že ak súčet pravdepodobností n-tice udalostí je viac ako k-1 (pre akékoľvek k od 1 do n), tak sa s nenulovou pravdepodobnosťou realizuje aspoň k spomedzi týchto udalostí.

Napríklad ak by sme mali skupinku piatich ľudí, pričom (pravdepodobnosť, že prvý z nich spraví skúšku) + (pravdepodobnosť, že druhý z nich spraví skúšku) + ... + (pravdepodobnosť, že piaty z nich spraví skúšku) > 3, tak potom s nenulovou pravdepodobnosťou sa stane to, že skúšku spravia aspoň štyria z týchto piatich ľudí. Pritom nepredpokladáme, že udalosti urobenia skúšky sú nezávislé. (Nakoniec, predpokladať úplnú nezávislosť vypracovávania písomnej časti skúšky by naozaj bolo značne naivné.)

Na ilustračnom obrázku sú štyri množiny (mesiačiky A,B,C a kruh D), pričom neexistuje prienik všetkých štyroch. To znamená, že ak by sme akokoľvek divoko hádzali šípkou do tohto obrázka, tak súčet pravdepodobností zasiahnutia jednotlivých oblastí nemôže byť väčší ako 3.

Telepat II

Tentokrát nášmu telepatovi zaplatíme za každý uhádnutý symbol 1 euro. Telepat si postupne prikladá na čelo jednotlivé obálky, pričom vždy po chvíľke telepatovania danej obálky povie svoj tip, čo by sa v nej malo nachádzať. Vypočítajte strednú hodnotu jeho zisku, ak nemá žiadne telepatické schopnosti, avšak má dokonalú pamäť a pritom používa optimálnu stratégiu tipovania. Uvažujeme nasledovné spresnenia:

a) Počas tipovania nedostáva telepat žiadnu informáciu o obsahu obálok, t.j. všetky obálky sa otvoria až po ukončení jeho tipovania. b) Po každom tipe sa daná obálka otvorí a telepat sa dozvie, ktorý symbol v nej bol. c) Po každom tipe prezradíme telepatovi len to, či uhádol, alebo neuhádol, avšak nie to, ktorý konkrétny symbol sa v danej obálke nachádzal.

Riešenie ani jednej z týchto troch úloh nie je úplne triviálne (pokiaľ človek nenájde správny trik), preto sú veľmi vítané akékoľvek nápady, riešenia pre malé n, prípade simulačné výsledky.

Namiesto ilustračného obrázku mám dnes pre Vás link od Juraja.

Poznámka 27.8.: Ak som sa nepomýlil, tak tie stredné hodnoty zisku pri optimálnej stratégii vychádzajú vo všetkých troch prípadoch celkom pekne. Ak si s tým problémom neviete poradiť, pokúste sa aspoň odhadnúť, či pre rastúce n (n je počet rôznych symbolov, t.j. aj počet obálok) ide stredná hodnota zisku pri optimálnej stratégii do nekonečna, alebo naopak, či existuje hranica, ktorú stredná hodnota zisku nepresiahne pre žiadne n ani pri tej najlepšej stratégii. Čo hovorí Vaša intuícia?

Telepat

Tieto dni je mojou hlavnou pracovnou náplňou dokončovanie zbierky príkladov z teórie pravdepodobnosti, ktorú musíme čoskoro odovzdať do tlače. Pri spisovaní riešenia jedného príkladu ma napadla takáto netechnická formulácia vhodná aj na náš blog:

Telepat bez akýchkoľvek telepatických schopností, ktorému bolo navyše nečakane znemožnené podvádzať, sa snaží určiť n rôznych symbolov nachádzajúcich sa na kartách v n nepriehľadných obálkach. (Telepat vopred vie, aké symboly boli náhodne rozdistribuované do obálok; nevie len to, v ktorej obálke je ktorý symbol. Telepat teda priradí obálkam n-ticu symbolov úplne náhodne a až potom sa všetky obálky otvoria, aby sa zistilo, koľko symbolov uhádol.) Čo je pravdepodobnejšie: to, že neuhádne ani jeden symbol, alebo to, že uhádne práve jeden symbol?

Na ilustratívnom obrázku sú takzvané Zenerove karty, ktoré sa často používajú na testovanie proklamovaných telepatických schopností. V našom zadaní je však počet kariet všeobecné n, t.j. nielen 5. Teším sa na Vaše riešenia.