Gostei! Muito interessante o problema.
Em vez de contar a quantidade de litros que cada posto tem, vamos contar a distância que o total de gasolina do posto permite o carro andar.
Sejam {1, ..., n} (mod n) os postos e x_i > 0 é a "quantidade" de gasolina (no sentido acima) no posto i.
Sabemos por hipótese que x_1 + ... + x_n = C, onde C é o comprimento do circuito.
Seja d_i a distância do posto i ao posto i+1 (mod n, ou seja d_n é a dist. de x_n a x_1), claramente
d_1 + ... + d_k = C.
Seja k o posto com maior valor de x_k/d_k.
Claramente x_k/d_k >= 1, caso contrário, x_i < d_i para todo i e isso é uma contradição.
Agora a prova segue por indução!
Forme um novo circuito sem o trecho entre os postos k e k + 1.
No lugar do trecho e dos dois postos de gasolina, colocamos um único posto, cuja quantidade de gasolina é x_k + x_{k-1} - d_k > 0.
Note que o novo circuito formado tem tamanho C - d_k, a capacidade dos postos é C - d_k e a soma das distâncias entre postos consecutivos é C - d_k. Aplique a hip. indutiva e veja que se é possível percorrer o circuito formado então o circuito original também pode ser percorrido.
O caso base é n = 1, que é trivial!
Olá pessoal !
Em uma pista circular há postos de gasolina, e o total de gasolinaquehá nos postos é exatamente o suficiente para um carro dar uma volta.Prove que existe um posto de onde um carro com o tanque inicialmente vazio pode partir e conseguir dar uma volta completa na pista (parando para reabastecer nos postos).
========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
