Re: [obm-l] Problema dos cocos

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Thu, May 01, 2003 at 10:38:28AM -0300, Fábio Nunes Ribeiro Maia wrote:
> Obrigado pela solução, Nicolau. Mas eu estou no Ensino Médio e não entendi
> por que "a seqüência de informações que temos amarra o valor de N módulo
> 5^6", e também por que "os valores possíveis de N
> são 5^6*k - 4". Poderia explicar melhor o que você fez? A resposta está
> certa, mas a resolução não ficou muito clara pra mim...

Vamos lá de novo então...

Depois da primeira divisão temos N1 = 4*(N-1)/5 = (4/5)N - (4/5) cocos.
Depois da segunda, N2 = 4*(N1 - 1)/5 = (16/25)N - (36/25)
e depois N3 , N4 e N5 definidos por fórmulas similares.
Finalmente cada um ganha M = (N5 - 1)/5 cocos.
Mesmo sem fazer as contas é óbvio que existe uma fórmula para M 
que tem a seguinte cara: M = (a/5^6)N + (b/5^6) onde a e b são inteiros.
Mais exatamente, a = 4^5; o valor exato não é importante, o importante
é que a não é múltiplo de 5. Todo o problema consiste em fazer com que 
M seja inteiro, ou seja, com que a*N + b seja múltiplo de 5^6.
Ora, já vimos que isso deu certo para N = -4 (apesar de isso não
ter o chamado sentido físico): neste caso aliás
M = ((4^5)*(-4) + b)/(5^6) = -1.
Observe que daí é fácil tirar -(4^6) + b = -(5^6) e b = (4^6) - (5^6).
Mesmo sem calcular b é claro que vai continuar a dar tudo certo
para todo N da forma N = (5^6)*k - 4, k inteiro qualquer
(ou inteiro positivo, para haver sentido físico): teremos M = (4^5)*k - 1.
Também é claro que para outros valores inteiros de N o problema vai
dar errado pois M não será inteiro.

[]s, N.




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