Re: [obm-l] Problema do Camelo

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Rogerio:

Entendi a sua objecao e sou obrigado a concordar (com uma certa pena, pois
confesso que fiquei bem animado quando achei uma formula fechada - mais um
caso que demonstra que a solucao bonitinha nem sempre eh a correta!).
Uma outra forma de ver eh que, nessa minha estrategia, o camelo deixa
possivelmente uma pequena quantidade de agua em cada um dos n pontos
intermediarios, ou seja, eu deveria ter escrito que:
para depositar A = 100k - 1000(2k-1)/n litros de agua no ponto x+1000/n,
ele deveria ter, no ponto x, uma quantidade de agua >= 100k litros
(desigualdade ao inves de igualdade, jah que k eh necessariamente inteiro).
Assim, imagino que a soma das quantidades de agua restantes em cada um dos n
pontos seja responsavel pela diferenca de (4,85-4,61)*10^6 litros.

Nao vi a sua solucao, que imagino ser semelhante a do Nicolau, mas gostaria
principalmente de ver uma demonstracao de que eh de fato a otima.

Um abraco,
Claudio.

on 19.11.03 07:29, Rogerio Ponce at rogerio_ponce@hotmail.com wrote:

> Olá Claudio,
> infelizmente essa idéia não está exata, pois nem sempre o camelo sairá com
> 100 litros de um determinado ponto (pense na última viagem partindo do tal
> ponto) . Dessa forma , o "rendimento" dele não será o mesmo , e o resultado
> também não ( o resultado foi calculado no caso do camelo ter o melhor
> rendimento, que é carregar o máximo de água possível em cada viagem) .
> 
> Assim , podemos apenas afirmar que o resultado final será maior que o seu
> número.
> []'s
> Rogério.
> 
> 
> 
>> From: Claudio Buffara <claudio.buffara@terra.com.br>
>> Reply-To: obm-l@mat.puc-rio.br
>> To: <obm-l@mat.puc-rio.br>
>> Subject: [obm-l] Problema do Camelo
>> Date: Fri, 01 Jan 1904 11:13:40 -0200
>> MIME-Version: 1.0
>> Received: from sucuri.mat.puc-rio.br ([139.82.27.7]) by mc1-f9.hotmail.com
>> with Microsoft SMTPSVC(5.0.2195.6713); Tue, 18 Nov 2003 19:43:24 -0800
>> Received: (from majordom@localhost)by sucuri.mat.puc-rio.br (8.9.3/8.9.3)
>> id BAA01409for obm-l-MTTP; Wed, 19 Nov 2003 01:30:11 -0200
>> Received: from paiol.terra.com.br (paiol.terra.com.br [200.176.3.18])by
>> sucuri.mat.puc-rio.br (8.9.3/8.9.3) with ESMTP id BAA01405for
>> <obm-l@mat.puc-rio.br>; Wed, 19 Nov 2003 01:30:10 -0200
>> Received: from araci.terra.com.br (araci.terra.com.br [200.176.3.44])by
>> paiol.terra.com.br (Postfix) with ESMTP id CD2B88485D6for
>> <obm-l@mat.puc-rio.br>; Wed, 19 Nov 2003 01:29:40 -0200 (BRST)
>> Received: from [200.182.232.11] (23211.virtua.com.br
>> [200.182.232.11])(authenticated user claudio.buffara)by araci.terra.com.br
>> (Postfix) with ESMTP id 508B521EF49for <obm-l@mat.puc-rio.br>; Wed, 19 Nov
>> 2003 01:29:40 -0200 (BRST)
>> X-Message-Info: UZmYcfFpTCc8t1OtwQ0ZJ3A1IDd8cguk
>> User-Agent: Microsoft-Outlook-Express-Macintosh-Edition/5.02.2022
>> Message-ID: <9DE4.241B%claudio.buffara@terra.com.br>
>> In-Reply-To: <BAY9-F7osA91E9GQvnb00034baf@hotmail.com>
>> Sender: owner-obm-l@sucuri.mat.puc-rio.br
>> Precedence: bulk
>> Return-Path: owner-obm-l@sucuri.mat.puc-rio.br
>> X-OriginalArrivalTime: 19 Nov 2003 03:43:25.0244 (UTC)
>> FILETIME=[4954A7C0:01C3AE4F]
>> 
>> Uma ideia eh dividir o percurso de 1000 km em n trechos iguais (n > 20) e
>> fazer o camelo transportar a agua atraves de um trecho de cada vez (ou
>> seja,
>> o camelo transporta toda a agua necessaria de x = 0 ateh x = 1000/n atraves
>> de varias viagens entre estes dois pontos e, uma vez que tenha feito isso,
>> nunca mais volta para x = 0. Em seguida, transporta toda a agua para x =
>> 2000/n e nunca mais volta para 1000/n, e assim por diante)
>> 
>> Suponhamos que o camelo queira armazenar A litros de agua no ponto
>> (x+1000/n) por meio de viagens entre o ponto x e o ponto (x+1000/n).
>> Pergunta: Quanta agua deve existir no ponto x antes dele comecar esse
>> transporte?
>> 
>> O camelo sai de x com 100 litros e consome 1000/n litros para chegar em
>> (x+1000/n), deposita 100-2000/n litros, e consome mais 1000/n litros para
>> voltar ao ponto x, onde chega vazio.
>> 
>> Como ele comeca em x e termina em (x+1000/n), podemos considerar qe ele faz
>> (k-1) viagens de ida-e-volta e mais uma ultima viagem soh de ida, ao fim da
>> qual ele ainda terah 100-1000/n litros, os quais deposita em (x+1000/n).
>> 
>> Assim, ele deposita em (x+1000/n) uma quantidade de agua igual a:
>> A = (k-1)(100-2000/n) + (100-1000/n) = 100k - 1000(2k-1)/n.
>> 
>> O seu consumo eh igual a (k-1)(2000/n) + 1000/n = 1000(2k-1)/n.
>> Logo, deve existir inicialmente em x uma quantidade de agua igual a:
>> A + 1000(2k-1)/n = 100k litros.
>> 
>> Expressando k em funcao de A e n, obtemos: k = (A*n - 1000)/(100n - 2000).
>> Ou, seja, a quantidade inicial de agua eh 100k = (A*n - 1000)/(n - 20)
>> Para x = 1000 - 1000/n (o ultimo trecho), sabemos que A = 1000 litros.
>> Logo, deve haver 1000*(n-1)/(n-20) litros no ponto x = 1000 - 1000/n.
>> 
>> Assim, chamando a quantidade de agua que chega ao fim do j-esimo trecho
>> (1<=j<=n) de Q(n-j), teremos a recorrencia:
>> Q(0) = 1000
>> Q(1) = (n*Q(0)-1000)/(n-20) = 1000*(n-1)/(n-20)
>> ...
>> Q(j) = (n/(n-20))*Q(j-1) - 1000/(n-20)
>> Q(j-1) = (n/(n-20))*Q(j-2) - 1000/(n-20)
>> 
>> Subtraindo, obtemos:
>> Q(j) - Q(j-1) = (n/(n-20))*(Q(j-1) - Q(j-2)) ==>
>> Q(j) - (1 + n/(n-20))*Q(j-1) + (n/(n-20))*Q(j-2) = 0 ==>
>> 
>> Raizes do polinomio caracteristico: 1  e  n/(n-20) ==>
>> 
>> Q(j) = A + B*(n/(n-20))^j
>> 
>> j = 0 ==> Q(0) = A + B = 1000
>> j = 1 ==> Q(1) = A + (n/(n-20))*B = 1000*(n-1)/(n-20) ==>
>> 
>> A = 50; B = 950 ==>
>> 
>> Q(j) = 50 + 950*(n/(n-20))^j = 50 + 950*(1 + 20/(n-20))^j.
>> 
>> Queremos a quantidade inicial de agua, a qual eh dada por Q(n) ==>
>> Q(n) = 50 + 950*(1 + 20/(n-20))^n.
>> 
>> Para n > 20, Q(n) eh uma funcao decrescente de n. Logo, a fim de achar a
>> quantidade minima de agua, devemos fazer n tender a infinito.
>> Nesse caso, Q(n) tende a 50 + 950*e^20 = 460.906.935.689,3007640706514890 ~
>> 4,61 * 10^11 litros.
>> 
>> *****
>> 
>> Sem levar em conta a falta de realismo do problema, eu nao estou convencido
>> de que a solucao acima eh de fato a minima, pois eh possivel que haja uma
>> estrategia de distribuicao da agua pelo percurso que utilize uma quantidade
>> menor de agua do que 4,6*10^11 litros (em outras palavras, uma estrategia
>> que minimize a distancia total percorrida pelo camelo).
>> 
>> 
>> Um abraco,
>> Claudio.
>> 

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