Re: [obm-l] Adivinhe o seu bit

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

On Mon, Oct 06, 2003 at 05:21:05PM -0300, Cláudio (Prática) wrote:
> > 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?
> 
> É isso mesmo. Eu devia ter deixado mais explícito no enunciado, mas se elas
> pudessem se comunicar livremente o problema seria trivial.

Eu já mandei uma estratégia para n = 3 e ninguém mais tocou no assunto depois.

O melhor que me ocorre é o seguinte. Numeremos as rodadas a partir de 1.
Suponha que você vê k pessoas com o bit a e (n-k-1) pessoas com o bit b,
onde k <= (n-k-1). Se k = (n-k-1) então você passa sempre.
Por outro lado se k < (n-k-1), então a sua estratégia é a seguinte.
Nas jogadas 1, 2, ..., k você passa;
se o jogo chegar à rodada (k+1) então você chuta que o seu bit é a.

Por exemplo, se você vê todo mundo com o bit b então na primeira jogada
você chuta que o seu bit é a. Mas se você vê (n-2) pessoas com o bit b
e uma pessoa com o bit a então você pula a primeira rodada para ver se
o cara com o único a que você vê chuta; se ele não faz isso é pq ele vê
um outro a---obviamente o seu! Na segunda rodada você "chuta" que o seu
bit é a, mas isso não deveria realmente se chamar "chutar", você joga
com a certeza de que vai ganhar (supondo que as outras pessoas sigam
a estratégia corretamente).

Não é difícil provar que se um grupo seguir esta estratégia então ele só perde
se todo mundo tiver o mesmo bit, ou seja, com probabilidade 1/2^(n-1).
Isto resolve o problema. Tenho quase certeza de que esta é a melhor
estratégia possível mas não pensei em como demonstrar este fato.

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