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

 

Outros conteúdos desta edição

Outros conteúdos nesta categoria

614_256 att-22975
614_256 att-22985
614_256 att-22993
614_256 att-22995
614_256 att-22987
614_256 att-22991
614_256 att-22989
614_256 att-22999
614_256 att-22983
614_256 att-22997
614_256 att-22963
614_256 att-22937
614_256 att-22931
614_256 att-22965
614_256 att-23039