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