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 =========================================================================
