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 3From: "Qwert Smith" <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] 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
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" <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] To: <[EMAIL PROTECTED]> 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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em nome de Qwert Smith Enviada em: quinta-feira, 11 de dezembro de 2003 17:33 Para: [EMAIL PROTECTED] 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" <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: <[EMAIL PROTECTED]> >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 =========================================================================
