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

["Will" <will@xxxxxxxxxx>]

Esse problema é conhecido como "problema de Josephus" e está destrinchado em
detalhes no excelente "Concrete Mathematics", do Knuth (e Patashnik, creio
eu).

A solução enxuta envolve converter n para binário e "girar" um bit, por
exemplo.

99 prisioneiros = 64+32+2+1 -> 1100011  (em binário)

"girando" o bit da esquerda, temos 1000111, que é 64+4+2+1 = 71

Logo basta estar na posição 71 :-)

Em particular quando o número é da forma 2^n é trivial ver que vence o
primeiro a dar uma espadada.

Lógico que não estou explicando muito em apenas mostrar o resultado, mas
está tudo explicado no Concrete. (Eu mesmo não sei o argumento agora, de
cabeça)

Will



----- Original Message -----
From: "Douglas Ribeiro Silva" <douglasrsilva@bol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, December 11, 2003 11:11 PM
Subject: [obm-l] RES: [obm-l] Círculo da Morte


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


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