*38. Suponha que em um grupo de carros em uma pista circular exista combustível suficiente para um carro completar a volta. Use a indução matemática para mostrar que há um carro no grupo que pode completar uma volta obtendo o combustível dos carros enquanto ele atravessa a pista.

Passo 1

Resumo do enunciado: temos n+1 carros dispostos em sequência numa pista circular de comprimento L. Cada carro C_i carrega uma certa quantidade de combustível f_i, e
\sum_{i=1}^{n+1} f_i = L.
Precisamos mostrar que existe um carro que, partindo de sua posição com seu combustível inicial e pegando todo o combustível dos carros por onde passa, consegue dar a volta completa na pista. O método será indução em n.

Passo 2

Base da indução n=1: se há apenas um carro, dizemos C_1 com f_1=L. Obviamente C_1 completa a volta apenas com seu próprio combustível. Logo a propriedade vale para n=1.

Passo 3

Hipótese de indução: suponha que, sempre que tivermos n carros cujos combustíveis somam exatamente L, existe um deles que consegue completar a volta coletando combustível dos demais.

Passo 4

Passo indutivo: considere agora n+1 carros C_1,C_2,\dots,C_{n+1} com
\sum_{i=1}^{n+1} f_i = L.
Faça C_1 partir de sua posição, rodando no sentido horário e, ao encontrar cada carro C_i, transfira todo o combustível f_i para C_1.
– Se C_1 completar a volta, terminamos.
– Caso contrário, C_1 fica sem combustível ao alcançar algum carro C_k, isto é, ele para exatamente em C_k antes de fechar o circuito.

Passo 5

Agora vamos reduzir o problema para n carros. Remova completamente C_k do grupo e transfira o seu combustível original f_k para o carro imediatamente seguinte C_{k+1} (índices em módulo n+1). Assim restam n carros e a soma dos combustíveis continua sendo
\bigl(\sum_{i=1}^{n+1}f_i\bigr)-f_k + f_k = L.
Pelo passo indutivo, desse novo grupo de n carros existe um veículo, digamos C_m, que consegue completar a volta na pista hipótética que também tem comprimento L.

Passo 6

Mostramos que C_m consegue também completar a volta na configuração original de n+1 carros. Ao partir de C_m, nos dois cenários ( n e n+1 carros) C_m vai pegando exatamente o mesmo combustível até chegar em um ponto que, no cenário reduzido, seria C_{k+1}, onde já estava somado o f_k.
No cenário original, C_k está presente em algum ponto imediatamente antes de C_{k+1}, e ao chegar em C_k o carro C_m recebe o combustível f_k. Assim, em todo instante o tanque de C_m na situação original contém pelo menos o mesmo volume que no cenário reduzido. Como nesse cenário reduzido ele completa a volta, também o fará no cenário real.

Resposta

Portanto, por indução, em qualquer grupo de carros cujo combustível total seja exatamente suficiente para um carro dar a volta, existe sempre um carro que consegue completar a volta pegando combustível dos demais.

Exercícios de Livros Relacionados