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