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, [EMAIL PROTECTED] 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).
>
>
