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