Re: [obm-l] postos de gasolina

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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