*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
carros dispostos em sequência numa pista circular de comprimento
. Cada carro
carrega uma certa quantidade de combustível
, e
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
.
Passo 2
Base da indução
: se há apenas um carro, dizemos
com
. Obviamente
completa a volta apenas com seu próprio combustível. Logo a propriedade vale para
.
Passo 3
Hipótese de indução: suponha que, sempre que tivermos
carros cujos combustíveis somam exatamente
, existe um deles que consegue completar a volta coletando combustível dos demais.
Passo 4
Passo indutivo: considere agora
carros
com
Faça
partir de sua posição, rodando no sentido horário e, ao encontrar cada carro
, transfira todo o combustível
para
.
– Se completar a volta, terminamos.
– Caso contrário, fica sem combustível ao alcançar algum carro
, isto é, ele para exatamente em
antes de fechar o circuito.
– Se
– Caso contrário,
Passo 5
Agora vamos reduzir o problema para
carros. Remova completamente
do grupo e transfira o seu combustível original
para o carro imediatamente seguinte
(índices em módulo
). Assim restam
carros e a soma dos combustíveis continua sendo
Pelo passo indutivo, desse novo grupo de
carros existe um veículo, digamos
, que consegue completar a volta na pista hipótética que também tem comprimento
.
Passo 6
Mostramos que
consegue também completar a volta na configuração original de
carros. Ao partir de
, nos dois cenários (
e
carros)
vai pegando exatamente o mesmo combustível até chegar em um ponto que, no cenário reduzido, seria
, onde já estava somado o
.
No cenário original,
está presente em algum ponto imediatamente antes de
, e ao chegar em
o carro
recebe o combustível
. Assim, em todo instante o tanque de
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.