21 augusta 2009

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.

8 komentárov:

Vladimír povedal(a)...

Principom zapojenia a vypojenia by sa mali dat obe pravdepodobnosti spocitat. V limite to bude asi nieco s "e"-ckami.

Brano povedal(a)...

no pocitat sa mi to nechce poriadne ale co takto takyto (pochybny) argument

p_n pravdepodobnost, ze uhadne prave jednu z n
q_n pravdepodobnost, ze uhadne prave nula z n

p_n = n*q_n-1 ~(pre velke n)~ nq_n
teda p_n > q_n

Radoslav Harman povedal(a)...

Vlado: Máš pravdu, pomocou princípu zapojenia-vypojenia by to išlo a nebolo by to ani také ťažké. Ale možno to ide aj nejakým trikom, pomocou ktorého nemusíme explicitne vyjadriť tie obe pravdepdobnosti...

Braňo: Nejaké takéto rekurencie by mohli byť pri riešení užitočné, ale tá, ktorú si napísal, zdá sa neplatí. Napríklad q_2 je 1/2, ale p_3 určite nie je 3/2.

Brano povedal(a)...

aha jasne chyba. skusme znova.

q_n*(n-1)! pocet permutacii s nula spravnymi
na n miest sa da pridat to jedno spravne
teda n*q_n*(n-1)! je pocet permutacii s prave jednou spravnou a to sa rovna p_n*n! teda
p_n=q_n-1>q_n

Radoslav Harman povedal(a)...

Braňo: Zdá sa, že naozaj platí p_n=q_{n-1} a Tvoje zdôvodnenie je jasné (hoci tam sú malé preklepy; q_n má byť q_{n-1}), ale ako si prišiel na to, že q_{n-1}>q_n?

misof povedal(a)...

Rado, daj si pozor na formulaciu v zbierke, v tomto zadani chyba ze (predpokladam) telepat najskor tipne celu permutaciu az potom moze otvarat obalky. Moze to byt zavadzajuce, lebo AFAIK Zenerove karty sa praveze bezne pouzivaju tak, ze "telepat" vzdy hada len jednu.

Inak, celkom zlata je aj na prvy pohlad totozna uloha: "Co je pravdepodobnejsie: to, ze uhadne vsetkych N symbolov, alebo to, ze ich uhadne prave N-1?"

Ako vravim, na prvy pohlad to vyzera byt skoro ta ista uloha, ale zato na druhy... ;)

Radoslav Harman povedal(a)...

Mišo: V zbierke je tá formulácia dosť odlišná. Ale ďakujem za upozornenie, pre istotu to skontrolujem. Keď sa snažím napísať zadanie neformálne, tak sa mi málokedy podarí napísať ho na prvýkrát úplne presne. Je to tým, že v skutočných situáciách vždy existujú nejaké mnou neodhadnuté, ale celkom reálne okolnosti, ktoré zamýšľané zadanie menia.

Tá Tvoja úloha je pekná, ale v tej mojej je aspoň niečo treba naozaj aj počítať :-)

Radoslav Harman povedal(a)...

Mišo: Už som tú Tvoju poznámku zakomponoval do zadania. Samozrejme, že ak aj telepat vždy háda len symbol v jednej obálke, no po tipnutí si mu nedáme žiadnu informáciu ohľadom toho, či uhádol, alebo nie a ak naviac dodržuje to, že každý symbol si tipne práve raz, tak je situácia rovnaká ako v zadaní.

Rozdiel by bol napríklad vtedy, ak by sme po každom jeho tipe obálku otvorili a ukázali mu, čo v nej bolo. V tomto prípade by bola síce pravdepodobnosť uhádnutia všetkých symbolov rovnaká ako v pôvodnom zadaní, ale napríklad pravdepodobnosť q_n neuhádnutia žiadneho symbolu by bola 0 (minimálne posledný symbol určite uhádne) v porovnaní s naším zadaním, kde q_n konverguje k nenulovému číslu. Takže rozdiel je tam podstatný.

Každopádne je jasné, že na túto tému sa dá vymyslieť veľa ďaších zaujímavých úloh. Asi napíšem aj Telepata II.