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