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.