Crise do petróleo
REVISTA CH 229 :: AGOSTO DE 2006 :: QUAL O PROBLEMA?
Como dar uma volta completa em uma pista circular sem que acabe a gasolina?
Hoje em dia, muitos se preocupam com a próxima crise do petróleo, mas ninguém sabe exatamente quando ela vai acontecer e quais serão suas conseqüências. Mas uma coisa é certa: vai ocorrer! E um dos principais problemas será a falta de gasolina (Há, claro, outras maneiras de faltar gasolina; uma delas ? bem mais comum que as crises internacionais ? é quando o motorista esquece de abastecer o tanque, e o próximo posto fica longe...).
Este mês, imaginaremos um mundo mais simples, onde há apenas uma pista circular (ou seja, nunca ocorrem engarrafamentos, e ninguém nunca se perde!). Nela, há um número arbitrário de postos de gasolina em posições igualmente arbitrárias, e a única coisa que se sabe (e isso é uma imposição do problema) é que a quantidade total de gasolina em todos os postos é suficiente para se dar uma volta completa na pista. O motorista (no caso, você, leitor) sabe o número de postos, a localização de cada um deles, quanta gasolina tem em cada posto e que o total de combustível é exatamente o necessário para se dar uma volta completa. Inicialmente, o tanque está vazio.
O problema deste mês é: será possível escolher um posto de modo que, partindo dele, seremos (estou de carona) capazes de dar uma volta completa na pista? Note a dificuldade do problema: um dos postos pode ter só uma gotinha de gasolina... e o próximo pode estar muito longe!
Comecemos com um exemplo simples, porém instrutivo. Suponha que a pista tenha 10 km, que o carro ande 1 km por litro (não é muito eficiente...) e que tenhamos só dois postos, um com 2 litros e outro com 8 litros. Coloque os postos a uma distância de 1 km no sentido horário. Digamos que você queira dar uma volta no sentido horário também. Que posto escolher? Nesse caso, é claro que você tem que partir do posto com 2 litros, chegando ao outro com 1 litro no tanque, que, somado aos 8 dele, permite completar uma volta. Mas, para rodarmos no sentido anti-horário, teríamos que partir do posto com 8 litros, chegando ao outro com 7 no tanque. Esses 7, somados aos 2 do outro posto, permitiriam completar a volta. Então, nesse caso específico, nosso problema está resolvido. E no geral?
O princípio para a solução geral está nesse caso simples. Primeiro, vamos mostrar que é sempre possível escolher um posto com gasolina suficiente para chegar ao seguinte. Isso tem que ser verdade, porque, se não fosse, a gasolina do primeiro posto não seria suficiente para ir até o segundo; a do segundo não seria suficiente para ir até o terceiro, e assim por diante; ou seja, a gasolina total não seria suficiente para dar uma volta completa!
Então concluímos que existe um posto com gasolina para chegar até o seguinte. Como a gasolina dele é suficiente para ir até próximo, podemos pensar em 'uma pista com um posto a menos', juntando a gasolina desses dois postos em um só (nos exemplos acima, podemos reduzir a situação com dois postos àquela com apenas um). A pista com N-1 postos ainda continuará tendo gasolina para se dar uma volta.
A nova pista (N-1 postos) também terá pelo menos um posto cuja gasolina nos permitirá ir até o seguinte. Podemos, portanto, transformá-la em uma pista com N-2 postos. E assim por diante. Com isso, podemos reduzir um problema com N postos àquele em que há nela apenas um posto, e este sempre terá gasolina suficiente para se dar uma volta.
Nosso problema está resolvido! Não sei se é porque a pista era circular, mas até fiquei um pouco tonto depois dessa...
Desafio
A solução desse problema usou um método 'da frente para trás' (N, N-1, N-2...). Você conseguiria resolvê-lo ao contrário, ou seja, mostrar que, se ele vale para N postos, também valerá para N+1, N+2 e assim por diante?
Solução do desafio passado
Escolha uma pessoa qualquer, chame-a de 1. Agora, trace as linhas dela para as outras 16, usando as três cores à disposição. Devemos ter pelo menos seis pessoas unidas a 1 (desafio: por quê?) por linhas da mesma cor (azul, por exemplo). Se duas delas estiverem unidas por azul, então está feito o triângulo azul (formado por elas duas mais a pessoa 1). Portanto, essas seis pessoas só podem estar unidas por linhas de duas cores. Mas esse é exatamente o problema da coluna passada, e, sendo assim, existirá um triângulo da mesma cor.
Marco Moriconi
Instituto de Física,
Universidade Federal Fluminense
- A Petrobras E O Aumento Do Combustível
O combustível brasileiro que já não é barato, especialmente o óleo diesel e a gasolina tiveram reajuste. A justificativa é de que a Petrobrás exporta óleo cru e importa o combustível já refinado, pois lamentavelmente temos baixo investimento...
- R$ 2,99 O Litro Da Gasolina É Um Absurdo!!!
E aí??? Você é mais um cidadão indignado com essa palhaçada que virou os preços dos combustíveis? R$ 2,99 O LITRO DA GASOLINA É UM ABSURDO!!! Então vamos nos unir e mostrar para esses oportunistas que quem manda nessa palhaçada, somos nós consumidores....
- Gasolina Cara Demais
Preços da gasolina, etanol e GNV irão aumentar em maio em Santa CatarinaReajuste é consequência da atualização da tabela utilizada pela Secretaria da Fazenda para cobrar o ICMSFelipe Pereira | [email protected] Acredito que não exista...
- Impostos E Demagogia: O Liberalismo é Contra O Estado Forte... As Vezes Não
A notícia (?) pode ser lida aqui: Esta já é a 6ª edição do Dia da Liberdade de Impostos, em que o litro da gasolina será vendido a R$ 1,25. Até às 7h50 dessa terça-feira já haviam 86 carros na fila em frente ao posto Firenze, da rua Santana,...
- Se O álcool Substituir A Gasolina, Faltará Comida No Mundo?
Lorena Verli Mesmo se 100% da gasolina fosse substituída por álcool, não faltariam terras para plantar gêneros alimentícios suficientes para alimentar o mundo inteiro. Mas a questão não é tão objetiva assim, afinal os alimentos não são distribuídos...