[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] O PROBLEMA DE JOSEFUS!



Olá Felipe,
existe algum problema com sua solução.

Suponhamos seis prisioneiros, com Josefus em quarto lugar.
Para n=6 e J=4 , obtemos q=1 .
Assim, pela ordem de eliminação, sairiam os prisioneiros 1,2,3,4 e 5,
sobrando o sexto, que certamente ficaria muito agradecido a Josefus...

[]'s
Rogério.


>From: Felipe Rangel
>
>Ola Jorge e demais colegas,
>
>Essa questao do josefus tem uma resposta muito elegante:
>
>Josefus podera sempre se safar se ele escolher q da maneira mostrada 
>abaixo:
>Seja 2^x a unica potencia de 2 pertencente no intervalo n/2<=2^x<=n-1,
>J>=2*(n- 2^x) implica q=J - 2*(n- 2^x) + 1,
>J<2*(n- 2^x) implica q=J - 2*(n- 2^x) + 1 + n,
>
>Eu nao vou mostrar a justificativa, so para incentivar mais pessoas a 
>responder.
>
>
>Sds, Felipe Rangel.
>
>jorgeluis@edu.unifor.br wrote:
>Ok! Pessoal! Vejam uma variante de um problema antigo em homenagem a 
>Flavius
>Josefus, um historiador famoso do primeiro século. Segundo a lenda, Josefus 
>não
>teria sobrevivido para ficar famoso se não fosse seu talento matemático. 
>Durante
>a guerra entre judeus e romanos, ele estava entre 11 rebeldes judeus
>encurralados em uma caverna pelos romanos. Preferindo o suicídio à captura, 
>os
>rebeldes decidiram formar um círculo e, contando ao longo deste, matar cada
>terceira pessoa restante até não sobrar ninguém. Mas Josefus, junto com um
>co-conspirador não identificado, não queria saber deste pacto suicida; 
>então
>calculou rapidamente onde ele e seu amigo deveriam ficar neste círculo 
>maligno.
>
>Na nossa variação, começamos com n pessoas numeradas de 1 a n em um círculo 
>e
>eliminamos cada segunda pessoa restante até sobrar uma única pessoa. 
>Suponha
>que Josefus se encontra em uma determinada posição J, mas tem a chance de 
>dizer
>qual é o parâmetro de eliminação q tal que toda q-ésima pessoa é executada. 
>Ele
>sempre pode se salvar?
>
>Vocês sabiam...que o quadrado de um número inteiro não pode terminar em 
>mais de
>três algarismos iguais a 4...
>
>
>Abraços!
>

_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.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
=========================================================================