Ola Rogerio de demais colegas desta lista ... OBM-L,
O que eu deve entender por "ele deve beber ( continuamente ) um litro de agua por quilometro" ?
Vou supor que o Oasis e o marco zero ( zero quilometro ).
IMAGINE que o camelo esta no Oasis. Ele e entao carregado com 100 litros agua. Ao atingir o marco 1, ele andou 1 quilometro e, portanto, vai beber 1 litro de agua. Ao atingir o marco 2, bebe mais um litro. Sobram entao 98 litros dos 100 litros com que ele partiu. Ele deixa 97 no marco 2 e volta. Ao atingir o marco 1, bebe o ultimo litro de que dispoe. Andando mais um kilometro ele chega ao Oasis, onde ha agua em abundancia e, portanto, bebe um litro desta agua.
Assim, saindo com N litros do Oasis, N =< 100, ele pode deixar 100 - 2K + 1 litros no marco K
( K =< 50 ) e o Oasis ficou reduzido em 101 litros de agua. Como ha agua em abundancia no Oasis, repetindo esta operacao um grande numero de vezes ele pode colocar ate um "Oceano de Agua" no marco K, isto e, a partir de um certo momento ele nao precisa mais voltar ao oasis original ... Ele vai poder partir sempre do marco K.
Mas nos queremos o minimo de agua que deve ter no oasis original. Seja M esse minimo. Posso portanto supor, com base na observacao acima, que apos um numero finito de vezes, R, o oasis foi "deslocado" para o marco K, isto e, no marco K ha "M - 101R" ( para algum R natural e supondo que ele sempre parte com 100 litros ) o oasis original estara vazio e, portanto, o camelo nao deve e nao precisa voltar ao oasis original.
E possivel usar esta estrategia ? Ou o camelo sempre precisa voltar ate o Oasis original ?
Nao esta claro isto no texto !
Existe um outro problema. O que e "beber continuamente" ?
Suponha que o camelo parte com 100 litros de agua e vai ate o ponto raiz_quadrada(2). Devo supor que ele bebeu raiz_quadrada(2) litros de agua ? Neste caso ao atingir o marco K ( K inteiro ) e voltar ele dixa 100 - 2K, consumindo 2k litros de agua, isto e, quando, na volta, ele atingir o oasis, ele ja consumiu 2K litros de agua e nao, como parece, 2K-1. Note que, neste caso, precisamos supor alguma coisa sobre a "forma" do caminho que liga o oasis ao sindicato, pois, bebendo continuamente, ele vai beber menos se a ligacao oasis-sindicato for um segmento de reta ...
Existe um outro problema. O que e "ele pode deixar depositos de agua em qualquer lugar do caminho" ?
O camelo so pode deixar agua em marcos quilometricos inteiros ? ou, por exemplo, ele pode se dirigir uma posicao R, R real, depositar 100 - 2R de agua ali. Neste caso "absolutamente continuo", isto e, onde o camelo bebe continuamente e pode depositar agua em qualquer posicao real, me parece que e melhor substituir o camelo ...
SALVO UM MELHOR JUIZO, que eu apreciaria ver, me parece que o problema quer usar um detalhe matematico que nao se coaduna convenientemente com o contexo usado ou foram admitidos pressupostos que nao ficaram suficientemente claro no enunciado.
O problema e bonito e engenhoso e imaginar uma forma de levar 1000 litros ate a posicao 1000 e bastante facil, mesmo trivial. Mas determinar uma estrategia otima no sentido de consumir uma quantidade minima de agua nao me parece um problema simples, sobretudo porque nao esta claro quais pressupostos podemos admitir ...
From: "Rogerio Ponce" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: [obm-l] O problema do camelo
Date: Sun, 16 Nov 2003 21:18:44 +0000
MIME-Version: 1.0
X-Originating-IP: [200.214.109.236]
X-Originating-Email: [EMAIL PROTECTED]
Received: from mc2-f16.hotmail.com ([65.54.237.23]) by mc2-s1.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Sun, 16 Nov 2003 13:20:12 -0800
Received: from sucuri.mat.puc-rio.br ([139.82.27.7]) by mc2-f16.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Sun, 16 Nov 2003 13:20:11 -0800
Received: (from [EMAIL PROTECTED])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) id TAA16393for obm-l-MTTP; Sun, 16 Nov 2003 19:19:17 -0200
Received: from hotmail.com (bay9-f38.bay9.hotmail.com [64.4.47.38])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) with ESMTP id TAA16388for <[EMAIL PROTECTED]>; Sun, 16 Nov 2003 19:19:15 -0200
Received: from mail pickup service by hotmail.com with Microsoft SMTPSVC; Sun, 16 Nov 2003 13:18:44 -0800
Received: from 200.214.109.236 by by9fd.bay9.hotmail.msn.com with HTTP;Sun, 16 Nov 2003 21:18:44 GMT
X-Message-Info: TiNwL5K19MHsk4VxzSki9pnCOmcwpv/nq0oFfSMx1Cw=
Message-ID: <[EMAIL PROTECTED]>
X-OriginalArrivalTime: 16 Nov 2003 21:18:44.0576 (UTC) FILETIME=[375AB600:01C3AC87]
Sender: [EMAIL PROTECTED]
Precedence: bulk
Return-Path: [EMAIL PROTECTED]
Repassando o problema do camelo...
Um camelo deve fazer uma entrega de 1000 litros de água ao Sindicato dos Beduínos, que fica a 1000 km de distância de seu oásis de partida. O camelo pode carregar até 100 litros de água e deve beber (continuamente) 1 litro de água por quilômetro. Ele pode deixar depósitos de água em qualquer ponto do caminho. De quanta água (no mínimo) ele precisa para cumprir sua missão?
-------------------------------
Li, e passei adiante esse problema há 3 dias. Algumas pessoas não entenderam adequadamente o enunciado, de forma que faço algumas observações:
1- O que se pretende é : qual o total mínimo da água necessária , no oásis de partida , para as sucessivas idas e vindas , alcançando pontos cada vez mais distantes, de forma a finalmente totalizar o transporte dos 1000 litros a 1000 km de distância.
2- O camelo só precisa LEVAR a água , isto é , não precisa fazer a última viagem de volta.
_________________________________________________________________
MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br
========================================================================= 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 =========================================================================
