Re: [obm-l] O problema do camelo
On Tue, Nov 18, 2003 at 02:43:31AM +, Rogerio Ponce wrote: também fiz as contas, e achei um resultado um pouquinho diferente: aproximadamente 485367037627.98265 litros ( cerca de 0,015 litros a menos ) Se eu não errei nada, o camelo precisa de aproximadamente 4.854 * 10^11 litros. Mais exatamente, 485367037627.9977897968 litros. As minhas contas foram feitas assim (no Maple): Digits := 80: g := n - harmonic(2*n - 1) - (1/2)*harmonic(n - 1): f := n - g(n) - g(10): A lógica disto é a seguinte. Se o camelo tem (n+1) hectolitros na posição x ele pode fazer (n+1) idas e n voltas de uma distância de 1/(2n+1) hectômetros gastando exatamente um hectolitro e portanto terminando com n hectolitros na posição x + 1/(2n+1). Mais geralmente, se ele começa com n hectolitros na posição x ele pode chegar com 10 hectolitros na posição x + f(n). Podemos resolver o que está acima para ver quantos hectolitros ele precisa para andar 10 hectômetros e chegar ao final com 10 hectolitros. p0 := evalf(f(4853670377)); p0 := 10.007417295017787976087370248970081201715719166673769017821123475\ 4288137 p1 := evalf(f(4853670376)); p1 := 9.9971158126093234794872476551279280643105507545332459025098132534\ 1295726 Assim 4853670376 hectolitros não bastam (ficam faltando aprox. 2.88 nanômetros no final). Assim o camelo precisa *primeiro* levar 4853670376 por uma distância de 2.88 nanômetros. Neste zigzag inicial ele precisa fazer 9707340753 viagens de 2.88 nanômetros cada uma o que consome (10 - p1)*(2*4853670376 + 1); .279977897968029198136812935729744728657858126445225571962248227248837 hectolitros de água. Agora é só somar. Não entendi de onde saiu o seu valor (um pouquinho menor). Claro que para um engenheiro o fato de estarmos discutindo quanta água um camelo gasta para fazer 9707340753 viagens de 2.88 nanômetros cada uma é a prova definitiva da nossa insanidade... :-) []s, N. = 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 =
Re: [obm-l] O problema do camelo
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 + 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
Re: [obm-l] O problema do camelo
Olá Paulo, a estratégia de andar 3 km e deixar 97 litros não funciona, pois o camelo precisa de água para voltar. Talvez fique mais fácil pensar no problema da forma como eu o repassei para alguns amigos : Uma base militar precisa levar 1000 litros de gasolina para um posto avançado no deserto, situado a 1000 km de distância da base. Será usado um jipe , cujo tanque tem a capacidade de 100 litros, e que consome 1 litro por quilômetro. Ele pode deixar depósitos de gasolina em qualquer ponto do caminho. De quantos litros, no mínimo, ele precisará para cumprir sua missão?o jipe leva no máximo 100 litros , porra ! E mais : ele não precisa voltar. A missão é entregar somente. Para isso , ele terá que sucessivas vezes ir e voltar , deixando depósitos ao longo do caminho, até conseguir, na última ida, completar a missão. -- Observações que fiz na outra lista após repassar o problema : O jipe leva no máximo 100 litros ! E mais : ele não precisa voltar. A missão é entregar somente. Para isso , ele terá que sucessivas vezes ir e voltar , deixando depósitos ao longo do caminho, até conseguir, na última ida, completar a missão. A gasolina que o jipe deixa é a sobra tirada do seu próprio tanque. Assim, ele poderia partir da base com tanque cheio, deixar 98 litros a 1 km da mesma , e voltar , por exemplo. []´s Rogério. PS: O número é astronômico, com certeza. Li esse problema ontem, e não sei ainda qual a solução. _ 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 =
Re: [obm-l] O problema do camelo
Ola Pessoal ! Leia a minha mensagem que voce vai ver que em nenhum momento eu falei em andar 3 Km. Mas, tudo bem. Entendi o que voce quer. Obrigado. Um abraco Paulo Santa Rita 3,1450,181103 From: Rogerio Ponce [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] O problema do camelo Date: Tue, 18 Nov 2003 14:50:57 + MIME-Version: 1.0 X-Originating-IP: [200.244.74.46] X-Originating-Email: [EMAIL PROTECTED] Received: from mc7-f4.hotmail.com ([65.54.253.11]) by mc7-s15.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Tue, 18 Nov 2003 06:55:09 -0800 Received: from sucuri.mat.puc-rio.br ([139.82.27.7]) by mc7-f4.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Tue, 18 Nov 2003 06:54:34 -0800 Received: (from [EMAIL PROTECTED])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) id MAA21367for obm-l-MTTP; Tue, 18 Nov 2003 12:51:36 -0200 Received: from hotmail.com (bay9-f7.bay9.hotmail.com [64.4.47.7])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) with ESMTP id MAA21363for [EMAIL PROTECTED]; Tue, 18 Nov 2003 12:51:32 -0200 Received: from mail pickup service by hotmail.com with Microsoft SMTPSVC; Tue, 18 Nov 2003 06:50:57 -0800 Received: from 200.244.74.46 by by9fd.bay9.hotmail.msn.com with HTTP;Tue, 18 Nov 2003 14:50:57 GMT X-Message-Info: TiNwL5K19MHf1feKAmjG+8cQq2J4R9ZCeusC9BX42Hk= Message-ID: [EMAIL PROTECTED] X-OriginalArrivalTime: 18 Nov 2003 14:50:57.0416 (UTC) FILETIME=[5FDF5880:01C3ADE3] Sender: [EMAIL PROTECTED] Precedence: bulk Return-Path: [EMAIL PROTECTED] Olá Paulo, a estratégia de andar 3 km e deixar 97 litros não funciona, pois o camelo precisa de água para voltar. Talvez fique mais fácil pensar no problema da forma como eu o repassei para alguns amigos : Uma base militar precisa levar 1000 litros de gasolina para um posto avançado no deserto, situado a 1000 km de distância da base. Será usado um jipe , cujo tanque tem a capacidade de 100 litros, e que consome 1 litro por quilômetro. Ele pode deixar depósitos de gasolina em qualquer ponto do caminho. De quantos litros, no mínimo, ele precisará para cumprir sua missão?o jipe leva no máximo 100 litros , porra ! E mais : ele não precisa voltar. A missão é entregar somente. Para isso , ele terá que sucessivas vezes ir e voltar , deixando depósitos ao longo do caminho, até conseguir, na última ida, completar a missão. -- Observações que fiz na outra lista após repassar o problema : O jipe leva no máximo 100 litros ! E mais : ele não precisa voltar. A missão é entregar somente. Para isso , ele terá que sucessivas vezes ir e voltar , deixando depósitos ao longo do caminho, até conseguir, na última ida, completar a missão. A gasolina que o jipe deixa é a sobra tirada do seu próprio tanque. Assim, ele poderia partir da base com tanque cheio, deixar 98 litros a 1 km da mesma , e voltar , por exemplo. []´s Rogério. PS: O número é astronômico, com certeza. Li esse problema ontem, e não sei ainda qual a solução. _ 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 = _ 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 =
Re: [obm-l] O problema do camelo
On Tue, Nov 18, 2003 at 01:14:48PM +, Paulo Santa Rita wrote: 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. Não. Beber continuamente significa que se ele sai do oasis com 100 litros e viaja 2 quilômetros ele bebeu 2 litros durante a ida e vai precisar beber mais 2 litros durante a volta. Ele só pode deixar um reservatório de 96 litros. 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. Deveria ser 100 - 2K e o Oasis ficou reduzido em 100 litros. Fora isso está certo. 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. Certo. ... 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 ... A idéia original do problema era o que você chama do caso absolutamente contínuo. A solução que eu mandei deixa bem claro que você tem razão, o problema não é nem um pouco realista por vários motivos. []s, N. = 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 =
Re: [obm-l] O problema do camelo
Ola Carissimo Prof Nicolau e demais colegas desta Lista ... OBM-L, Ok, entendi. Cheguei em casa agora. Como voce demonstrou entusiasmo, a solucao deve ser bonita. Vou me distrair com ele durante a noite. Um Abracao pra Voce Paulo Santa Rita 3,2215,181103 From: Nicolau C. Saldanha [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] O problema do camelo Date: Tue, 18 Nov 2003 16:51:41 -0200 MIME-Version: 1.0 Received: from mc11-f7.hotmail.com ([65.54.167.14]) by mc11-s2.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Tue, 18 Nov 2003 10:53:29 -0800 Received: from sucuri.mat.puc-rio.br ([139.82.27.7]) by mc11-f7.hotmail.com with Microsoft SMTPSVC(5.0.2195.6713); Tue, 18 Nov 2003 10:53:21 -0800 Received: (from [EMAIL PROTECTED])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) id QAA25882for obm-l-MTTP; Tue, 18 Nov 2003 16:51:41 -0200 Received: (from [EMAIL PROTECTED])by sucuri.mat.puc-rio.br (8.9.3/8.9.3) id QAA25877for [EMAIL PROTECTED]; Tue, 18 Nov 2003 16:51:41 -0200 X-Message-Info: TiNwL5K19MF+xJ1AW2VdvC67UzLr2wt521xIdiE+lto= Message-ID: [EMAIL PROTECTED] References: [EMAIL PROTECTED] User-Agent: Mutt/1.2.5i In-Reply-To: [EMAIL PROTECTED]; from [EMAIL PROTECTED] on Tue, Nov 18, 2003 at 01:14:48PM + Sender: [EMAIL PROTECTED] Precedence: bulk Return-Path: [EMAIL PROTECTED] X-OriginalArrivalTime: 18 Nov 2003 18:53:21.0752 (UTC) FILETIME=[3CF8E580:01C3AE05] On Tue, Nov 18, 2003 at 01:14:48PM +, Paulo Santa Rita wrote: 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. Não. Beber continuamente significa que se ele sai do oasis com 100 litros e viaja 2 quilômetros ele bebeu 2 litros durante a ida e vai precisar beber mais 2 litros durante a volta. Ele só pode deixar um reservatório de 96 litros. 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. Deveria ser 100 - 2K e o Oasis ficou reduzido em 100 litros. Fora isso está certo. 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. Certo. ... 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 ... A idéia original do problema era o que você chama do caso absolutamente contínuo. A solução que eu mandei deixa bem claro que você tem razão, o problema não é nem um pouco realista por vários motivos. []s, N. = 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 =
RE: [obm-l] O problema do camelo
Fiz as contas e não resisto. Se eu não errei nada, o camelo precisa de aproximadamente 4.854 * 10^11 litros. Mais exatamente, 485367037627.9977897968 litros. Isto é um pouco menos do que os 592731741234 encontrados na mensagem anterior (mas a ordem de grandeza estava certa). É completamente irreal imaginar que o camelo ainda vai estar vivo no final, claro. Aliás, que quantidade de água é esta (comparando com o volume de algum rio, por exemplo)? Eh aproximadamente a quantidade de agua que passa pelo rio Xingu em 18,6 horas, considerando-se a vazao media de longo termo (media aritmetica das vazoes mensais dos ultimos 60 anos) de 7231 m3/s. Na cheia, quando a vazao jah atingiu 28629 m3/s, este volume de agua passa em cerca de 4,7 horas. Mas na epoca da seca, seriam necessarias 552,6 horas ~= 23 dias para passar esta agua toda, considerando-se a vazao de 244 m3/s, a menor, em termos medios mensais, jah verificada desde 1931. Artur = 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 =
Re: [obm-l] 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? On Sun, Nov 16, 2003 at 10:52:34PM -0200, Fabio Dias Moreira wrote: Tá, eu entendo o seu raciocínio, mas eu interpretei o enunciado de maneira diferente da sua: estes reservatórios não vêm de graça e você não pode posicioná-los arbitrariamente ao início do processo; o deserto está inicialmente vazio e o camelo deve fazer excursões a partir de seu oásis-base para montar estes reservatórios no meio do deserto. Estabelecer reservatórios custa água. Óbvio, posso ter entendido o enunciado errado. Caso o tenha feito, a sua solução está perfeita. Oi lista, eu tenho ficado calado sobre este problema meio por preguiça. A interpretação que o Gugu e eu tínhamos em mente é a do Fabio, se eu bem entendi o que ele disse. Inicialmente não há nenhum reservatório e nenhuma água no deserto, toda a água está no ponto de partida do camelo. O camelo pode largar um ou mais tanques de água em qualquer ponto no meio do deserto e voltar lá mais tarde para buscar a água: ninguém rouba a água, a água não estraga nem evapora. É bem óbvio (dada a interpretação correta) que o camelo precisa fazer mitas viagens. Uma solução (não ótima) a seguinte: o camelo sempre pode botar nas costas até 100 litros de água, andar um quilômetro, depositar 98 litros, voltar e repetir a operação (os dois litros restantes foram consumidos pelo camelo). Assim, se queremos ter N litros de água e o camelo no quilômetro M+1 basta termos f(N) = N + 2k - 1 litros na posição M onde k é o menor inteiro maior ou igual a N/98. Assim, começando com f^1000(1000) litros conseguimos completar a missão. Fazendo as contas no maple isto dá: f := n - n + 2*ceil(n/98) - 1: a[0] := 1000: for i to 1000 do a[i] := f(a[i-1]): od: a[1000]; 592731741234 que *não* é a melhor resposta possível. Mas é verdade que esta coisa cresce exponencialmente e que a resposta vai ser grande. Fica como exercício para vocês procurar a solução ótima e demonstrar que ela é mesmo ótima. []s, N. = 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 =
Re: [obm-l] O problema do camelo
On Mon, Nov 17, 2003 at 09:39:14AM -0200, Nicolau C. Saldanha wrote: 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? Fiz as contas e não resisto. Se eu não errei nada, o camelo precisa de aproximadamente 4.854 * 10^11 litros. Mais exatamente, 485367037627.9977897968 litros. Isto é um pouco menos do que os 592731741234 encontrados na mensagem anterior (mas a ordem de grandeza estava certa). É completamente irreal imaginar que o camelo ainda vai estar vivo no final, claro. Aliás, que quantidade de água é esta (comparando com o volume de algum rio, por exemplo)? Mando a solução em outra mensagem. []s, N. = 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 =
Re: [obm-l] O problema do camelo
On 11/17/03 12:00:58, Nicolau C. Saldanha wrote: [...] Fiz as contas e não resisto. Se eu não errei nada, o camelo precisa de aproximadamente 4.854 * 10^11 litros. Mais exatamente, 485367037627.9977897968 litros. Isto é um pouco menos do que os 592731741234 encontrados na mensagem anterior (mas a ordem de grandeza estava certa). É completamente irreal imaginar que o camelo ainda vai estar vivo no final, claro. Aliás, que quantidade de água é esta (comparando com o volume de algum rio, por exemplo)? [...] Não é muita coisa. O reservatório de Itaipu tem 27 * 10^9 m^3 = 27 * 10^12 L. http://www.pbs.org/wgbh/buildingbig/wonder/structure/itaipu.html []s, -- Fábio ctg \pi Dias Moreira GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net) pgp0.pgp Description: PGP signature
Re: [obm-l] O problema do camelo
Olá pessoal, também fiz as contas, e achei um resultado um pouquinho diferente: aproximadamente 485367037627.98265 litros ( cerca de 0,015 litros a menos ) []'s Rogério Ponce PS: Demonstrar uma solução ótima é simples mas dá trabalho - mando depois. On Mon, Nov 17, 2003 at 09:39:14AM -0200, Nicolau C. Saldanha wrote: 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? Fiz as contas e não resisto. Se eu não errei nada, o camelo precisa de aproximadamente 4.854 * 10^11 litros. Mais exatamente, 485367037627.9977897968 litros. Isto é um pouco menos do que os 592731741234 encontrados na mensagem anterior (mas a ordem de grandeza estava certa). É completamente irreal imaginar que o camelo ainda vai estar vivo no final, claro. Aliás, que quantidade de água é esta (comparando com o volume de algum rio, por exemplo)? Mando a solução em outra mensagem. []s, N. _ 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 =
Re: [obm-l] O problema do camelo
Oi Rogério. O enunciado deste problema está ERRADO, pois do modo como ele está, não tem solução. Seja eps 0. Não é difícil mostrar que o camelo pode cumprir sua tarefa começando com eps litros de água. Basta colocar o primeiro posto a eps/2 de distância e, no resto do caminho, dispor postos para que ele possa cumprir seu objetivo. Como eps positivo foi escolhido arbitrariamente, não há mínimo. 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. 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, 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. É impossível que ele cumpra sua missão com exatamente 1100 litros de água, pois neste caso ele não poderia andar para trás. Também não há mínimo, portanto. Abraço, Duda. From: Rogerio Ponce [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 = = 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 =
Re: [obm-l] O problema do camelo
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 + 2/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 + 2/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 =
Re: [obm-l] O problema do camelo
On 11/16/03 22:13:16, Eduardo Casagrande Stabel wrote: 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 + 2/n. [...] Tá, eu entendo o seu raciocínio, mas eu interpretei o enunciado de maneira diferente da sua: estes reservatórios não vêm de graça e você não pode posicioná-los arbitrariamente ao início do processo; o deserto está inicialmente vazio e o camelo deve fazer excursões a partir de seu oásis-base para montar estes reservatórios no meio do deserto. Estabelecer reservatórios custa água. Óbvio, posso ter entendido o enunciado errado. Caso o tenha feito, a sua solução está perfeita. []s, -- Fábio ctg \pi Dias Moreira GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net) pgp0.pgp Description: PGP signature
