Re: [obm-l] postos de gasolina

[Faelccmm@xxxxxxx]

Obrigado, Domingos !


Falando em indução, se tiverem algum material (apostila on-line, endereço na internet, etc...) onde eu possa estudar isto, agradeceria muito. Eu até encontrei algumas coisas, mas eu gostaria de algum paper que tivesse MUITOS EXERCÍCIOS DE FIXAÇÃO. Dos que encontrei há apenas 2 exemplos (exercício), na maioria das vezes aquele exemplo da soma de uma P.A ;-)   
Se não me engano é um dos axiomas de Peano, não é isso ?


Em uma mensagem de 16/10/2004 11:04:25 Hora padrão leste da Am. Sul, dopikas@uol.com.br escreveu:


> 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).
> >
> >