On 11/16/03 21:03:05, Eduardo Casagrande Stabel wrote:
[...] Se a pergunta é: quanta água ele precisa *no total* para cumprir sua missão?
Ainda assim, o problema não tem solução. Seja eps > 0. Dispomos os
postos
com uma quantidade de gasolina de forma que o camelo chegue até "eps"
quilômetros do objetivo final, com exatamente 100 litros de água. [...]
Isso exige que se monte um reservatório na posição 1000-eps, já que a capacidade máxima do camelo é exatamente 100 (i.e. a água que ele leva é recém-obtida).
[...] Ele vai até o seu objetivo e despeja (100 - 2*eps) litros de água e ainda tem eps consigo, então ele volta eps/2 quilômetros, se reabastece, [...]
Mas se reabastece aonde? Você não falou nada de reservatórios na posição 1000 - eps/2.
e retorna
ao
final. Dessa forma (se bem organizado) ele pode ter precisado andar
exatamente 1000 + eps quilômetros, consumido 1000 + eps litros de água
e
levado 100 litros até o final, tendo utilizado 1100 + eps litros de
água. [...]
Mas ainda faltam 900 litros. O camelo deve transportar 1000 litros, e não apenas 100.
Eu sei demonstrar que a tarefa é possível por indução: seja d a distância que o camelo deve percorrer. É obvio que para d = 1 a tarefa é possível. Suponha que é possível fazê-la com V litros. Então de uma distância d+1, basta "empurrar" 98 litros de cada vez até a distância d, de tal forma que haja pelo menos V litros de água em d, logo agora é possível concluir a tarefa.
Eu acho que a solução passa por alguma idéia deste gênero, com um incremento apropriado. Eu conjecturo que o incremento que dá o meior rendimento é 25.
[]s,
-- Fábio "ctg \pi" Dias Moreira GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net)
pgp00000.pgp
Description: PGP signature
