Re: [obm-l] mais uma!

["David Turchick" <davidturchick@xxxxxxxxxxx>]

Primeiro note que podemos alterar levemente as regras, de modo que elas nos 
convenham e o tempo mínimo não se altere. Em vez de "algumas das amebas 
dividem-se em sete novas amebas", podemos impor "todas as amebas dividem-se 
em sete novas amebas". É melhor ver isso com um exemplo (eu comecei a 
escrever mas tava ficando grande e chato):
Para ir de 6 amebas para 25 amebas o mais rápido possível, vc pode tanto 
fazer:
6 -> 5 -> 4 -> 28 -> 27 -> 26 -> 25, como
6 -> 30 -> 29 -> 28 -> 27 -> 26 -> 25, e ambas são feitas no menor tempo 
possível. (Não provei, mas acho que dá p/ entender o que eu tô fazendo, 
tendo pensado um pouquinho no problema. Caso contrário, diga.)

Agora o problema. A resposta é 9 segundos:
Primeiro veja que dá p/ fazer nesse tempo: 1 -> 7 -> 6 -> 42 -> 41 -> 287 -> 
286 -> 2002 -> 2001 -> 2000.
Agora tente fazer em menos (digamos em t<9 segundos). De trás p/ frente: 
como 2000 não é divisível por 7, em t-1 teríamos que ter 2001 amebas (aqui 
foi útil aquela mudança nas regras). Como 2001 não é divísivel por 7, em t-2 
teríamos que ter 2002. Em t-3, temos ou 2003 ou 2002/7=286. Mas se fosse 
2003, seguindo esse raciocínio teríamos em t-8 2008, mas t-8<9-8=1, isto é, 
t-8 é o tempo 0, contradição. Então em t-3 temos 286, e em t-4, 287. Em t-5 
temos que ter 287/7=41, pois senão temos 288, e vai demorar mais 6 passos 
até chegarmos num múltiplo de 7, estourando os 9 segundos. Etc.

David

>From: "Adherbal Rocha Filho" <adherbalmat@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: [obm-l] mais uma!
>Date: Fri, 02 Aug 2002 21:36:27 +0000
>
>
>
>
>ae pessoal, mais uma questão pra qm quiser tentar:
>1.Em um tubo de ensaio há exatamente 1 ameba.A cada segundo algumas das 
>amebas devidem-se em sete novas amebas ou morre exatamente uma das 
>amebas.Determine o período mínimo de tempo após o qual o nº de amebas no 
>tubo de ensaio será igual a 2000.
>
>Blz!
>Adherbal
>
>_________________________________________________________________
>MSN Photos é a maneira mais fácil e prática de editar e compartilhar sua 
>fotos: http://photos.msn.com.br
>
>=========================================================================
>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
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================




_________________________________________________________________
MSN Photos é a maneira mais fácil e prática de editar e compartilhar sua 
fotos: http://photos.msn.com.br

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================