Problema
(Indicado a partir do 1º ano do E. M.)
Mostre que em todo subconjunto de [tex]\{1,2,3,…,2n\}[/tex], com [tex]n+1[/tex] elementos, há sempre um par de números, pelo menos, tais que um deles divide o outro.
Solução
Todo elemento [tex]x[/tex] do conjunto pode ser escrito como o produto de uma potência de [tex]2[/tex] por um número ímpar, [tex]x=2^k t[/tex], sendo [tex]t[/tex] ímpar e [tex]k[/tex] um inteiro não negativo.
Há, no máximo, [tex]n[/tex] valores possíveis para [tex]t: 1, 3,…,2n-1[/tex], e o conjunto tem [tex]2n[/tex] elementos; logo, pelo Princípio da Casa dos Pombos(*), haverá pelo menos dois números com o mesmo valor de [tex]t[/tex]. Deste modo, aquele número que tiver o menor expoente [tex]k[/tex] será divisor do outro.
 |
(*)Se você não conhece o Princípio das Casas dos Pombos, visite esta Sala |
Solução elaborada pelos Moderadores do Blog.