Eu conheço o método de aplicação do PIF para equações e inequações algébricas, mas na hora, não imaginei poder usár o PIF em um problema daquele tipo...
Valeu por me explicar! =)
Um abraço,
Cesar Ryudi Kawakami
At 16:39 22/10/2003, you wrote:
No fundo a culpa foi minha... não percebi que nível 2 é da 8ª série :-)
O tipo de prova que eu usei é bem comum, é a aplicação de um princípio matemático chamado PIF (princípio da indução finita). Vou tentar ser didático para explicá-lo.
Imagine que você tenha uma proposição baseada em um número inteiro, essa proposição depende de um inteiro "n", por exemplo: "Para todo número n de cidades conectadas como no enunciado abaixo, é possível obter um ciclo através dela trocando de transporte no máximo 1 vez".
O PIF requer que: - seja provado para um ou mais casos inciais que a afirmação seja verdadeira - supondo que a afirmação seja verdade para um intervalo de inteiros a partir do(s) caso(s) inciais, demonstre que ela é verdadeira para o primeiro inteiro fora do intervalo da suposição.
Se você conseguir fazer as duas coisas você mostrou que a proposição vale para todo n a partir do caso incial provado.
Vamos ver um exemplo besta: Mostre que 2^n < n! para n >= 4.
o caso incial é n = 4 e temos 2^4 = 16 < 4! = 24 suponha agora que isso seja verdade para todo k, com 4 <= k <= n ou seja, temos como hipótese que 2^n < n! bem, (n+1)! = (n+1)n! > 2n! (pois n >= 4) mas n! > 2^n, logo (n+1)! > 2*2^n = 2^(n+1)
provamos então pelo PIF que 2^n < n! para todo n >= 4.
Um detalhe técnico muito importante em que muita gente falha na hora de usar o PIF é que devemos estar atentos a hipótese usada, por exemplo, no caso acima bastou usar o fato de que 2^n < n! mas, se precisássemos além disso afirmar que 2^(n-1) < (n-1)!, deveríamos demonstrar na base os 2 primeiros valores (4 e 5), se isso não for feito a demonstração está errada!
========================================================================= 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 =========================================================================