RE: [obm-l] RES: [obm-l] Círculo da Morte

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

hehe... bem ki eu podia ter lido a mensagem do Rogerio antes de responder 
... teria economizado dedo... correcao va abaixo


>From: "Qwert Smith" <lord_qwert@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: RE: [obm-l] RES: [obm-l] Círculo da Morte
>Date: Fri, 12 Dec 2003 14:00:46 -0500
>
>
>Do jeito ki vc propos e 1/99 ja ki vc disse ki a espada seria entregue a um 
>prisioneiro
>
>aproveitanto para responder a) e b)
>
>a) o principe deve entrar na posicao 73
>
>b) a formula geral para k pessoas e:
>
>sendo k = 2^n + m, onde 2^n <= k <= 2^(n+1) e m inteiro nao negativo
>
>a posicao sobrevivente sera sempre 1 + 2m
>
>aplicando em a)
>2^6 <= 100 <= 2^7, logo
>100 = 64 + 36
>posicao sobrevivente = 1 + 2*36 = 73
>
>Prova ( aki e a parte ki nao me garanto muito... qualquer ajuda e bemvinda 
>)
>
>1) para todo k=2^n, a posicao 1 e a sobrevivente porque ao fim de cada 
>volta o numero de sobreviventes e 2^(n-v) -- v = numero de voltas dadas, e 
>a espada volta a posicao inicial
>
>2) agora vamos ver oke acontece para qualquer k = 2^n + 1
>
assim ki a primeira pessoa morre temos 2^n sobreviventes e de 1) sabemos que 
a pessoa que recebe a espada esta an posicao vencedora, como cada morte 
envolve 2 posicoes a posicao sobrevivente e a 3

>quando a espada chega na ultima posicao os sobriviventes sao 2^(n-1) + 1
>agora repare que quando o ultimo mata o primeiro temos de novo o numero de 
>sobreviventes do tipo 2^n logo a posicao que recebe a espada nessas 
>condicoes e a sobrevivente como vimos em 1)
>essa posicao e a posicao 3 ja ki temos ki pular nao so posicao 1 ki acaba 
>de morrer como tb a posicao 2 ki foi morta por 1 na primeira rodada.
>
>3) (aki e ki nao sei se o passo e muito grande, e gostaria de ajuda de quem 
>esta acostumado com questoes de provar isso ou aquilo)
>para k = 2^n + m

assim ki m pessoas morrem temos a situcao de 1) e como 2*m posicoes 
participam das mortes a posicao sobrevivente e 1 + 2*m

>temos k = 2^n + 1 + 1 + ... + 1 ( onde 1 parece m vezes )
>quando a espada chega na posicao 2^n + 1 temos uma situacao como em 2) e 
>sabemos ki a proxima morte faz a posicao vencedora pular 2 casas... so ki 
>agora ainda temos (m-1) participantes sobrando e podemos repetir o 
>raciocinio de pular 2 casas ate restarem apenas 2^(n-1) sobreviventes onde 
>teremos a posicao sobrevivente ate o fim do jogo.
>
>acho ki e so isso
>
>-Auggy
>
>
>
>>From: "Douglas Ribeiro Silva" <douglasrsilva@bol.com.br>
>>Reply-To: obm-l@mat.puc-rio.br
>>To: <obm-l@mat.puc-rio.br>
>>Subject: [obm-l] RES: [obm-l] Círculo da Morte
>>Date: Thu, 11 Dec 2003 23:11:58 -0300
>>
>>É verdade... só que eu sem querer propus errado. Desculpe ehehehhe
>>
>>Alem do que creio que você se enganou, no caso seria 1/100 porque o
>>príncipe é o 100º participante do circulo.
>>
>>Na hora que eu escrevi estava com um pouco de pressa e acabei me
>>enganando... Corrigindo a proposição da probabilidade:
>>
>>Se a espada fosse entregue aleatoriamente para algum dos "k"
>>prisioneiros só depois do príncipe entrar no círculo, qual a
>>probabilidade dele ficar vivo no final?
>>
>>
>>
>>
>>
>>-----Mensagem original-----
>>De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br] Em
>>nome de Qwert Smith
>>Enviada em: quinta-feira, 11 de dezembro de 2003 17:33
>>Para: obm-l@mat.puc-rio.br
>>Assunto: RE: [obm-l] Círculo da Morte
>>
>>hmmm... a c) pareece facil de responder...tao facil ki deve estar
>>errado...
>>vamos supor ki o principe entra na posicao x... essa posicao so
>>sobrevive se
>>o prisioneiro que receber a espada estive em uma outra posicao y
>>(relativa a
>>x)... portanto as chance sao 1/99 de sobreviver, ja que tem 99
>>prisioneiros
>>e so uma resultaria em sucesso para o principe
>>
>>
>> >From: "Douglas Ribeiro Silva" <douglasrsilva@bol.com.br>
>> >Reply-To: obm-l@mat.puc-rio.br
>> >To: <obm-l@mat.puc-rio.br>
>> >Subject: [obm-l] Círculo da Morte
>> >Date: Thu, 11 Dec 2003 16:53:09 -0300
>> >
>> >Esse eu achei muito interessante... Eu poderia encurtar tudo mas vou
>> >contar a historia como me foi proposta...
>> >
>> >Durante ter vencido uma longa guerra, um Rei fez como prisioneiros 99
>> >dos guerreiros de seu inimigo. Ele estava disposto a matá-los, mas não
>> >queria tirar suas vidas sem propósito. Arrumou então uma desculpa de
>> >casar sua filha, oferecendo a mão da moça a qualquer príncipe que
>> >aceitasse um desafio proposto por ele. Um certo dia um príncipe vindo
>>de
>> >muito longe chegou ao reino e pediu a mão da moça. Prontamente, o Rei
>> >disse que teria que passar por um desafio e o príncipe aceitou. Então o
>> >Rei lhe explicou qual era a situação:
>> >
>> >“Eu tenho 99 prisioneiros de guerra no calabouço. Irei dispô-los em
>> >forma circular, e darei uma espada a um deles. Logo após disso você irá
>> >adentrar no círculo em qualquer lugar que queira. O homem a receber a
>> >espada irá matar o que estiver a sua esquerda e passará a espada para o
>> >próximo a sua esquerda também. Este, que recebeu a espada, fará o
>>mesmo.
>> >Matará o que está a sua esquerda e passará para o próximo, e assim
>> >sucessivamente até sobrar uma única pessoa no círculo. Se você for o
>> >último terá então a mão da minha filha.”
>> >
>> >a)      Considerando o homem que recebeu a espada como o nº 1, o da sua
>> >esquerda o nº 2, e assim por diante, Em que posição do círculo o
>> >príncipe deverá ficar para permanecer vivo?
>> >b)      E se o círculo tivesse “k” pessoas? Qual o que permaneceria
>> >vivo?
>> >
>> >Essa aqui não faz parte da questão mas eu fiquei curioso e resolvi
>> >propô-la: Se a espada fosse entregue aleatoriamente para algum dos 99
>> >prisioneiros só depois do príncipe entrar no círculo, qual a
>> >probabilidade dele ficar vivo no final?
>> >
>> >Eu resolvi o a) e o b) na época que me foram propostos, mas obtive a
>> >fórmula geral por tentativas e queria uma solução mais “higiênica”. A
>> >outra pergunta que eu propus não soube como resolver.
>> >
>> >Abraços, Douglas
>>
>>_________________________________________________________________
>>Take advantage of our best MSN Dial-up offer of the year — six months
>>@$9.95/month. Sign up now! http://join.msn.com/?page=dept/dialup
>>
>>========================================================================
>>=
>>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
>>========================================================================
>>=
>>
>>
>>=========================================================================
>>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
>>=========================================================================
>
>_________________________________________________________________
>Get holiday tips for festive fun. 
>http://special.msn.com/network/happyholidays.armx
>
>=========================================================================
>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
>=========================================================================

_________________________________________________________________
Tired of slow downloads and busy signals?  Get a high-speed Internet 
connection! Comparison-shop your local high-speed providers here. 
https://broadband.msn.com

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