Re: [obm-l] O problema do camelo

[Fabio Dias Moreira <fabio.dias.moreira@xxxxxxxxxxxx>]

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)

PGP signature