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

Código: Selecionar tudo

[tex3]n \subset M[/tex3]

um dos números procurado, escrito da forma dos produtos dos 9 primeiros primos (antes de 26) :

Código: Selecionar tudo

[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,

Código: Selecionar tudo

[tex3]a_1,a_2 \cdots a_9[/tex3]

um número binário, então a quantidade é de

Código: Selecionar tudo

[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

Código: Selecionar tudo

[tex3]a_1,a_2,..., a_9[/tex3]

são zeros ou uns.