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