Re: [obm-l] Adivinhe o seu bit

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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
=========================================================================