Re: [obm-l] Adivinhe o seu bit

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

----- Original Message -----
From: "Nicolau C. Saldanha" <nicolau@sucuri.mat.puc-rio.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, October 06, 2003 4:04 PM
Subject: Re: [obm-l] Adivinhe o seu bit


> 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.
>
Oi, Nicolau:

É isso mesmo. Eu devia ter deixado mais explícito no enunciado, mas se elas
pudessem se comunicar livremente o problema seria trivial.

Um abraço,
Claudio.




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