Posted By: Xofon (Xof) on 'CZriddles'
Title:     Z Jarni skoly - reseni III
Date:      Thu May  4 17:29:45 2006


     Prichazi vzorove reseni prikladu III.

     Pravdepodobnost je nezavisle na zvolene strategii vzdy 1/2.

     Trikove zduvodneni: 

     Pravidla trochu pozmenime. O vyhrani/prohrani se bude rozhodovat ne 
podle prvni neodkryte karty, ale podle posledni. 
Pozorovani 1: Je to jen kosmeticka uprava, ktera pravdepodobnosti nezmeni. 
Pozorovani 2: Pravdepodobnost vyhry v pozmenene hre je nezavisle na 
strategii 1/2. 

     Standardni zduvodneni (due to vitas):

Oznacim si pravdepodobnost vyhry nejlepsi strategie, kdyz je v balicku i 
cervenych a n vsech karet: P(i,n)                                      

Pak je jiste ze P(0,n) = 0 a P(n,n) = 1. 

pro 1<i<n je pak P(i,n) = max(i/n, i/n*P(i,n-1)+(n-i)/n*P(i-1,n-1))
                              ^    ^             ^--nestop & nasl. cerna (3)
                              |    `---- nestop a nasledujici je cervena (2)
                              `---rekne stop (1)                            

(1) pravdepodobnost ze nasledujici je cervena
(2) nejlepsi strategie kdyz otocena bude cervena
(3) nejlepsi strategie kdyz otocena bude cerna

Reseni takovehle rekurence je P(i,n) = i/n.
Toto dokazeme matematickou indukci:
1. pro i = 0 plati.
2. max(i/n, i/n * i/(n-1) + (n-i)/n*(i-1)/(n-1)) = ... = max(i/n, i/n) = i/n


     Xof
:wq