[obm-l] Problema do Camelo

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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