Pregunta de la Olimpiada sobre el principio de encasillamiento

Question

Dado un conjunto $M$ de $1985$ enteros positivos distintos, ninguno de los cuales tiene un primo divisor mayor que $26$ , demuestre que $M$ contiene al menos un subconjunto de cuatro elementos distintos, cuyo producto es la cuarta potencia de un entero.

Ni siquiera pude empezar.

Answer 1

Hay $9$ primos menos que $26$ .

Puedes mirar cada número entero $n$ como un binario $9$ -que le da el valor de cada $\alpha_i$ $\bmod 2$ al escribir $n$ como $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$ .

Por lo tanto, tenemos $1985$ tales listas. Demostraremos que hay dos de estas listas de modo que cuando las sumamos los nueve términos son múltiplos de $2$ . Esto está claro, ya que $1985>512=2^9$ que es el número total de listas posibles debe haber dos que sean iguales. Así que tomamos esas dos listas iguales, que representan números $a$ y $b$ . Eliminamos los números $a$ y $b$ de la lista y colocamos su producto $ab$ en una lista separada. Seguimos haciendo esto hasta que tengamos $511$ números de la primera lista.

Cuando terminemos de hacer esto la nueva lista tendrá $(1985-511)/2=737$ números. Así que tendremos en la nueva lista $737$ cuadrados. Todos estos números son de la $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$ . Y cada $\alpha_i$ está en paz. Convierte cada uno de estos números en binario $9$ -tupla donde término $i$ es la congruencia $\bmod 4$ de $\alpha_i$ .

Desde $737>512=2^9$ hay dos números que dan la misma lista. Por lo tanto, el producto de estos dos números es una cuarta potencia Esta prueba funciona para tan solo $1537$ números, pero el enunciado del problema dice $1985$ porque este es el problema $4$ (segundo más fácil) de la imo $1985$

Answer 2

Podría ser interesante mostrar el caso más general, es decir, si conocemos los divisores primos de todos los elementos en $M$ están entre $p_{1}, p_{2}, ..., p_{n}$ y $M$ tiene al menos $2^{n} \cdot 3 + 1$ elementos, entonces contiene al menos un subconjunto de cuatro elementos distintos cuyo producto es una cuarta potencia.

El truco consiste en asignar a cada elemento $m$ en $M$ con un $n$ -tupla $(x_{1}, x_{2}, ..., x_{n})$ , donde $x_{i}$ es una variable indicadora igual a $0$ si el exponente de $p_{i}$ en $m$ es par, y $1$ de lo contrario.

Como mi profesor explicó este problema, estas tuplas se convierten en nuestro objetos con el que considerar el principio de encasillamiento, y nuestro cajas son las posibles opciones de $0$ y $1$ para cada indicador. Entonces, por el principio de encasillamiento, tenemos que cada subconjunto de nuestro $2^{n}+1$ elementos de $M$ contiene dos elementos (distintos) con el mismo objeto, o $n$ -y, en consecuencia, el producto de estos dos elementos es un cuadrado.

Nuestro proceso consiste en eliminar repetidamente estos pares y sustituirlos por dos de los números posibles que nos quedan. Como $M$ tiene al menos $2^{n}\cdot 3 + 1$ elementos, podemos seleccionar al menos $2^{n}+1$ pares.

Ahora debemos considerar la $2^{n}+1$ números que son productos de los dos elementos de cada par. Podemos repetir el mismo argumento anterior una vez más, para tener cuatro elementos $a,b,c,d$ en $M$ donde $\sqrt{ab}\sqrt{cd}$ es un cuadrado perfecto. Entonces $abcd$ es una cuarta potencia, y se ha demostrado nuestro resultado.

En su caso, tenemos que $n=9$ , como $1985 > 3 \cdot 2^{9} + 1 = 1537$ .