Olimpíadas ⇒ (Senorense México-90) Casa dos Pombos

[ALANSILVA]

seja M um conjunto de 1900 inteiros positivos distintos, tais que nenhum deles tem um divisor primo maior a 26. Demonstre que M contém ao menos 2 elementos distintos cujo produto é um quadrado perfeito.

[Vinisth]

Olá ALANSILVA,

Seja [tex3]n \subset M[/tex3] um dos números procurado, escrito da forma dos produtos dos 9 primeiros primos (antes de 26) :
[tex3]n=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3} \cdots 23^{a_9}[/tex3]
Este número pode-se associar um número binário de 9 digitos, ou seja, [tex3]a_1,a_2 \cdots a_9[/tex3] um número binário, então a quantidade é de [tex3]2^9=512[/tex3] números binários.
O conjunto dos 1900 inteiros e pelo principio da casa dos pombos, temos no mínimo que 2 são números iguais, ou seja, existe outros dois números distintos dos quais o produto deles é um quadrado perfeito, pois cada número do primo respectivo ou o expoente é par ou é ímpar. Por isso resulta em um quadrado perfeito.

Abraço !

[Auto Excluído (ID:12031)]

Não necessariamente [tex3]a_1,a_2,..., a_9[/tex3] são zeros ou uns.