FANDOM


Existem alguns problemas em que precisamos usar Combinatória e Teoria dos Números para resolvê-lo.

Exemplo (OBM 2011 - 3ª Fase - Nível 2)Editar

Esmeralda escreveu uma lista de números inteiros positivos em uma folha de papel. Renan percebeu que todos os números da lista e todas as somas de qualquer quantidade de números distintos da lista não eram divisíveis por nenhum quadrado perfeito diferente de $ 1 $. Qual a quantidade máxima de números na lista de Esmeralda?

Solução: Comecemos com casos pequenos. Dá para montar uma lista com $ 2 $ números? Sim: $ 2,3 $.

Também conseguimos com três? Sim: $ 13,17,21 $.

Tem como a lista ter $ 4 $ ou mais números? Suponha que existam pelo menos quatro números nessa lista, que chamaremos de $ a,b,c $ e $ d $. Como $ 4 $ é quadrado perfeito, precisamos que nenhum destes números seja múltiplo de $ 4 $. Então os possíveis restos destes números na divisão por $ 4 $ são $ 1,2 $ ou $ 3 $. Pelo Princípio da Casa dos Pombos, existem dois destes números com o mesmo resto na divisão por $ 4 $. Podemos supor, sem perda de generalidade, que esses números são $ a $ e $ b $.

Observe que $ a $ e $ b $ não podem ter resto $ 2 $ na divisão por $ 4 $, pois isto faria com que $ a+b $ fosse múltiplo de $ 4 $. Desta forma, os restos na divisão de $ a $ e $ b $ por $ 4 $ são $ 1 $ ou $ 3 $. Em ambos os casos $ a+b $ possui resto $ 2 $ na divisão por $ 4 $.

Como $ a+b+c $ e $ a+b+d $ não podem ser múltiplos de $ 4 $, segue que $ c $ não podem ter resto $ 2 $ na divisão por $ 4 $, ou seja, os restos possíveis para estes números são $ 1 $ ou $ 3 $. Em ambos os casos, $ c+d $ deixa resto $ 2 $, fazendo com que $ a+b+c+d $ múltiplo de $ 4 $. Absurdo.

Logo, não é possível fazer essa lista com $ 4 $ ou mais elementos e a quantida máxima de números é $ 3 $.