FANDOM


Este princípio diz que todo subconjunto finito de $ \mathbb{N} $ possui um menor elemento. Ele é equivalente ao Princípio da Indução Finita.

Quando usar o Princípio da Boa Ordenação?Editar

Uma das maneiras é para mostrarmos que algo é falso para todo $ n $ natural. A estratégia é a seguinte: suponha que isto não seja falso sempre. Então o conjunto dos números com esta propriedade é diferente de vazio. Pelo Princípio da Boa Ordenação, ele possui um menor elemento. Use isto para encontrar um absurdo.

Exemplo (IMO 1988)Editar

Sejam $ a $ e $ b $ inteiros positivos tais que $ (1+ab)|(a^2+b^2) $. Mostre que $ \frac{a^2+b^2}{1+ab} $ deve ser um quadrado perfeito.

Solução: Vamos supor, por absurdo, que existam $ a $ e $ b $ inteiros tais que $ k=\frac{a^2+b^2}{1+ab} $ não seja quadrado perfeito. Tomemos estes dois números de forma que $ \operatorname{max}\{a,b\} $ seja o menor possível (ele existe por causa do Princípio da Boa Ordenação). Nosso objetivo será chegar em uma contradição: encontrar $ a' $ e $ b' $ tais que $ \operatorname{max}\{a',b'\} < \operatorname{max}\{a,b\} $.

Como conseguir estes outros números? Basta notarmos que $ k=\frac{a^2+b^2}{1+ab} \Leftrightarrow a^2-kab+b^2-k=0 (I) $. Existem dois valores de a que satisfazem esta equação. Aproveitaremos isto.

Mas vamos com calma. Primeiro precisamos mexer com $ \operatorname{max}\{a,b\} $. Depende se $ a $ é maior, menor ou igual a $ b $. Observe que $ a $ não pode ser igual a $ b $, pois se isto ocorresse, teríamos

$ k=\frac{2a^2}{1+a^2}<\frac{2a^2+2}{1+a^2}=2. $

Como $ k $ é natural, a única possibilidade é termos $ k=1 $, que é um quadrado perfeito, e não vale.

Sem perda de generalidade, podemos supor que $ a>b $. Assim, $ \operatorname{max}\{a,b\}=a $. Observe que além de $ a $, existe um inteiro $ a' $ que também satisfaz $ (I) $. Se pensar na soma e produto das raízes, este $ a' $ satisfaz

$ a+a'=kb $

$ aa'=b^2-k. $

Mas $ a' $ é natural? Basta analisarmos $ (I) $ para mostrarmos que $ a' \geq 0 $. Se provarmos que $ \operatorname{max}\{a',b\} < \operatorname{max}\{a,b\} $ chegaremos em uma contradição e terminaremos o problema.

Se provarmos que $ a'<b $, então

$ \operatorname{max}\{a',b\}=b<a= \operatorname{max}\{a,b\}. $

Como $ aa'=b^2-k $, então provar que $ a'<b $ equivale a mostrar que $ b^2-k<ab $. Mas sabemos que $ a>b $. Logo,

$ b^2-k<b^2<ab. $

BibliografiaEditar

  • E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.