Sobre los números interesantes

Question

Llamamos a un número natural muy interesante, si puede ser descompuesto en factores naturales, cada uno de los cuales está a menos de $30$. Demostrar que de $10000$ números interesantes, siempre podemos elegir dos, cuyo producto es un completo cuadrado.

Mi intento. El fin de un conjunto de $10000$ mil interesante números en orden ascendente $$ a_1 < a_2 < \ldots < a_{10000}. $$ Supongamos, que $a_1 < 10000$. Tomamos nota de que la estimación de $10000 = 100^2 < a_{10000}$. Entonces es claro que bajo estas restricciones hay un número$b < 100$,$b^2 = a_n$, $n \in \{1, \ldots,10000\}$.

Pero, ¿cómo demostrar si $a_1 \ge 10000$?

Answer 1

Interesantes números sólo pueden tener factores primos $<30$. Hay $10$ tales números primos. Para los efectos de este problema para cada uno de los interesantes número $n$ y cada uno de los prime $<30$ sólo es importante si este primer ocurre con un par o impar exponente en $n$. En otras palabras, los números interesantes considera que aquí se dividen en $2^{10}=1024$ clases ${}^*)$, por el producto de los dos números en la misma clase es un cuadrado. De ello se desprende que entre los $\geq1025$ números interesantes que hay un par de la especie.

${}^*)$ Cada uno muy interesante, $n$ es de la forma $n=2^{x_1}\cdot 3^{x_2}\cdot\ldots\cdot 29^{x_{10}}$. La paridad (par o impar) de la $x_k$ puede ser capturado en una palabra binaria de $(b_1,\ldots, b_{10})\in\{0,1\}^{10}$. Hay $2^{10}$ tales palabras.