Re: [obm-l] Problema do Camelo

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

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

_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.com

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