On Mon, Oct 06, 2003 at 03:25:46PM -0300, Cláudio (Prática) wrote: > São dadas n pessoas, cada uma com um bit (0 ou 1) escrito em sua testa de > forma aleatória e independente. Cada pessoa pode ver os n-1 bits escritos nas > testas das outras pessoas, mas não o seu próprio bit. O seguinte jogo é > jogado: cada pessoa escolhe ou PASSAR ou CHUTAR O SEU BIT, e isso é feito > simultaneamente por todas as n pessoas. Diremos que esse grupo de pessoas > VENCEU o jogo se pelo menos uma pessoa decidiu chutar o seu bit e todas as > pessoas que chutaram o seu bit acertaram. > > Mostre que: > 1) Para todo n >= 3 existe uma estratégia E(n) tal que: > Prob(vencer com E(n)) > 1/2 > > 2) Para todo n >= 1 existe uma estratégia E(n) tal que: > Prob(vencer com E(n)) --> 1 quando n --> infinito
Vejamos se eu entendi bem. As pessoas no grupo colaboram (ou todos ganham ou todos perdem). Elas podem combinar uma estratégia com antecedência mas uma vez iniciado o jogo elas não podem mais se comunicar (exceto pelas jogadas, que são públicas). A estratégia é escolhida antes do sorteio dos bits. É isso? Para n = 3 uma estratégia possível é a seguinte. Se os bits dos seus dois companheiros forem iguais chute que o seu é o oposto do deles. Assim se os três bits forem iguais o grupo perde na primeira jogada com três chutes errados; isto ocorre com probabilidade 1/4. Caso contrário o grupo ganha na primeira jogada, com um único chute (certo); isto ocorre com probabilidade 3/4. []s, N. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================