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" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> 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 =========================================================================