Re: [obm-l] Problema dos cocos

[Rafael <matduvidas@xxxxxxxxxxxx>]

Prof. Nicolau,

Usando seu raciocínio, fui resolver e cheguei num
final diferente para os cocos. Acho que o senhor se
esqueceu do último homem a pegar cocos! Veja minha
resolução:
Digamos que ele tinha N cocos no começo. Então vamos
escrever quantos cocos cada um tira e depois quanto
sobra tirando o que o homem tirou e o coco do macaco:
Havia = N
1° homem tirou 1 = N - 1
1° homem tirou 1/5 = 4.(N - 1)/5

Havia = 4.(N - 1)/5
2° homem tirou 1 = 4.(N - 1)/5 - 1
2° homem tirou 1/5 = 4.(4N - 9)/25

Havia = 4.(4N - 9)/25
3° homem tirou 1 = 4.(4N - 9)/25 - 1
3° homem tirou 1/5 = 4.(16N - 61)/125

Havia = 4.(16N - 61)/125
4° homem tirou 1 = 4.(16N - 61)/125 - 1
4° homem tirou 1/5 = 4.(64N - 369)/625

Havia = 4.(64N - 369)/625
5° homem tirou 1 = 4.(64N - 369)/625 - 1
5° homem tirou 1/5 = 4.(256N - 2101)/3125

Então no dia seguinte sobraram 4.(256N - 2101)/3125
cocos, de onde tirou-se um e dividiu por 5:
= [4.(256N - 2101)/3125 - 1]/5
= [(1024N - 8404)/3125 - 1]/5
= [(1024N - 8404 - 3125)/3125]/5
= (1024N - 11529)/15625

Cada um ficou com isso de cocos. Sabendo que isso é um
número inteiro temos que 1024N - 11529 tem que ser
divisível por 15625, que é a mesma coisa que
escrevermos:
1024x - 11529 = 0 (mod 15625)
1024x = 11529 (mod 15625)

E repare que se você tirar 15625 do lado direito terá:
1024x = 11529 (mod 15625)
1024x = -4096 (mod 15625)

E assim pode simplificar os dois lados por 1024:
1024x = -4096 (mod 15625)
x = -4 (mod 15625)

Somando novamente 15625:
x = -4 (mod 15625)
x = 15621 (mod 15625)

O menor número que deixa resto 15621 quando dividido
por 15625 é o próprio 15621. Então podiam haver 15621
cocos. O que daria o seguinte:
Havia 15621
Depois do 1° havia 12496
Depois do 2° havia 9996
Depois do 3° havia 7996
Depois do 4° havia 6396
Depois do 5° havia 5116

De onde tiraram um e dividiram entre os 5, cada um
ficando com mais 1023 cocos ao final.

Abraços,

Rafael.

 --- "Nicolau C. Saldanha"
<nicolau@sucuri.mat.puc-rio.br> escreveu: > On Thu,
May 01, 2003 at 12:49:58AM -0300, Fábio
> Nunes Ribeiro Maia wrote:
> > 299- Em uma ilha deserta havia cinco homens e um
> macaco. Durante o dia os
> > homens colheram cocos e deixaram a partilha para o
> dia seguinte. Durante a
> > noite, um dos homens acordou e resolveu pegar a
> sua parte. Dividiu a pilha de
> > cocos em cinco partes iguais, observou que sobrava
> um coco, deu esse coco
> > para o macaco, retirou e guardou a sua parte. Mais
> tarde, o segundo homem
> > acordou e fez a mesma coisa que o primeiro, dando
> também um coco para o
> > macaco. Sucessivamente, cada um dos três homens
> restantes fez o mesmo que os
> > outros dois, isto é, dividindo os cocos existentes
> em cinco partes iguais,
> > dando um coco para o macaco e guardando a sua
> parte. No dia seguinte, os
> > cinco homens repartiram os cocos em cinco partes
> iguais, observaram que
> > sobrou um coco, deram-no para o macaco e cada um
> pegou uma parte. Se N é o
> > menor número de cocos que a pilha inicial poderia
> ter, qual o menor valor de
> > N ?
> 
> Observe que N = -4 serve: cada homem dá um coco para
> o macaco, come -1 coco
> e a pilha volta a ter -4 cocos.
> 
> É claro que esta solução não serve, N deveria ser
> positivo.
> Mas é claro também que a seqüência de informações
> que temos
> amarra o valor de N módulo 5^6. Assim os valores
> possíveis de N
> são 5^6*k - 4 e o menor valor é 5^6 - 4 = 15621.
> Após cada divisão
> a pilha ficou com  12496, 9996, 7996 e 6396 cocos e
> na partilha final
> cada homem ganhou mais 1279 cocos.
> 
> []s, N.

_______________________________________________________________________
Yahoo! Mail
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam. 
http://br.mail.yahoo.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
=========================================================================