Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2

[Cesar Ryudi Kawakami <cesarkawakami@xxxxxxxxxx>]

Entendi...

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