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