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

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

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!

----- Original Message ----- 
From: "Cesar Ryudi Kawakami" <cesarkawakami@uol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, October 21, 2003 8:55 PM
Subject: Re: [obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2


Não entendi direito com que tipo de hipótese foi trabalhada...

Mais especificamente, não entendi como provar que tal suposição de que é
possível mudar de meio de transporte apenas uma vez para todo 1 <= k <= N -
1...

Haha, sou burro mesmo... =P

Um abraço,

Cesar Ryudi Kawakami


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