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.
[EMAIL PROTECTED] 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 =========================================================================
