[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [obm-l] RES: [obm-l] Círculo da Morte
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
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
=========================================================================