30 októbra 2009

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.)

7 komentárov:

Rori povedal(a)...

Ja by som dal 16 a kazdu inu. A preco si to myslim - dokaz nejak neviem :) Ale proste potrebujem donutit Bcko aby musel volit z co najvacsieho mnozstva kariet (a aby tie mali rovnaku sancu). V tomto pripade musi B volit z kariet 3 az 14...

Radoslav Harman povedal(a)...

Rori: Ak by hráč A mal 16 kartičiek a na každej iné číslo, tak by hráč B volil jednotku. (Hráč B, ako telepat, samozrejme vie, akú sadu kartičiek si pripravil hráč A.) V tomto prípade by vyhral hráč A len vtedy, ak si vyžrebuje lístok s číslom 2, čoho pravdepodobnosť je 1/16. To nie je až také zlé, ale existuje aj riešenie, pri ktorom hráč A vyhrá s väčšou pravdepodobnosťou.

Rori povedal(a)...

Uz viem kde je u mna chybicka - ja som si poplietol, ze kedy vyhra ktory hrac :)

joshu povedal(a)...

Ak som dobre pochopil zadanie, tak strategia, ze hrac a si napise cisla 2,3,5,6,8,9,11,12,14,15 (10 cisel, resp. viac takychto desatic dokopy) by mala priniest pre hraca A pravdepodobnost vyhry az 10%.
Tipujem, ze to je maximum, ale zatial bez dokazu...
Hrac B, ked si prepocita pravdepodobnosti, bude indiferentny vo volbe medzi 1,2,3,5,6,8,9,11,12,14,15,16.
Ale mozno sa mylim :)

Radoslav Harman povedal(a)...

joshu: vitaj na QED. Tvoje riešenie je nezanedbateľným zlepšením voči výberu každého čísla od 1 do 16 s rovnakou pravdepodobnosťou, ale stále to nie je optimum. Chce to ešte malé zdokonalenie Tvojej myšlienky.

joshu povedal(a)...

Veru, som sa unahlil...
Ale strategia pre hraca A:
2 3 6 7 10 11 14 15 (pripadne viac takychto osmic) prinesie sancu na vyhru 12,5% (teda 1/8). Hrac B v tomto pripade nema ziadne cislo, ktore by uprednostnil pred inymi.

A vdaka za privitanie, no nie som tu uplne novy, len mi to, neviem preco, dalo moju prezyvku miesto jozef.gabik :)

Radoslav Harman povedal(a)...

Jozef: fajn! Toto je už naozaj optimálne riešenie. Lukáš našiel riešenie pre všeobecné N (nielen pre N=16), ale jeho princíp je už celkom podobný.