Re: [obm-l] O problema do camelo

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

Oi Fábio!

Sim, a idéia é espalhar reservatórios, não há nenhuma restrição quanto a
colocar mais reservatórios.

Vou ser mais preciso quanto aos detalhes.

Seja n um número natural qualquer, n > 1000. Vamos dividir o caminho em
exatamente n pedaços de comprimento 1000 / n = eps cada um. Note que eps <
1. Suponha que ele parte da posição x = zero e quer chegar em x = 1000.

Ele começa com eps de água.
No reservatório em x = eps, há eps de água.
No reservatório em x = 2eps, há eps de água.
...
No reservatório em x = (n-2)eps = 1000 - 2eps, há eps de água.

Dessa forma ele se desloca até o ponto x = 1000 - eps tendo consumido
exatamente 1000 - eps de água.

Colocamos, então, muitos litros (já calcularei quantos) de água no
reservatório em x = (n-1)eps. O camelo vai até o final, em x = 1000, e lá
chega com 100 - eps, de água. Ele despeja, 100 - 2eps de água e permanece
com eps. Então ele volta até a posição x = 1000 - eps e se reabastece de 100
litros, indo até o final, e voltando a este ponto e assim sucessivamente.
Depois de dez indas e vindas, ele está na posição x = 1000 - eps, tendo
levado exatamente 1000 - 20eps para o final. Ele se abastece então de mais
21eps < 21 , e chega ao final, completando sua tarefa.

Nos postos x = 0 , eps, 2pes, ..., (n-2)eps tínhamos eps de água em cada.
No posto x = (n-1)eps tínhamos 100 * 10 + 21.eps de água.

O total é (n-1)*eps + 1000 + 21*eps = 2000 + 20*eps = 2000 + 20000/n.

A tarefa não pode ser completada com 2000 de água, pois isto implicaria que
o camelo andou só para frente e chegou ao final carregando 1000 litros de
água, o que fere as condições do enunciado. Mas 2000 + 20000/n pode ser
feito arbitrariamente próximo de 2000. Logo não há mínimo.

Eu me enganei achando que ele teria que levar 100 litros ao final, e não
1000. Agora já corrigi.

O que achas?

Abraço do Duda.


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)



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