Iberoamericana 2021 - Problema 1

[Matías V5]

Sea $P=\{p_1,p_2,\ldots ,p_{10}\}$ un conjunto de $10$ primos distintos y sea $A$ el conjunto de todos los enteros mayores que $1$ tales que en su descomposición en factores primos aparecen únicamente primos de $P$. Los elementos de $A$ se colorean de tal forma que:

a) cada elemento de $P$ tiene un color distinto,
b) si $m,n\in A$, entonces $mn$ tiene el mismo color de $m$ o $n$,
c) para cualquier par de colores distintos $\mathcal{R}$ y $\mathcal{S}$, no existen $j,k,m,n\in A$ (no necesariamente distintos), con $j,k$ de color $\mathcal R$ y $m,n$ de color $\mathcal S$, tales que $j$ divide a $m$ y $n$ divide a $k$, simultáneamente.

Demuestre que existe un primo de $P$ tal que todos sus múltiplos en $A$ tienen el mismo color.

[Sandy]

Spoiler: mostrar

Veamos primero por inducción en la cantidad de factores primos (no necesariamente distintos) que hay sólo $10$ colores. Cuando la cantidad de factores es $1$ es claro (pues son los $10$ primos). Si tenemos que para $t$ factores vale, sea $n=p_ik$ de $t+1$ factores. Debe ser por la condición b) que es o del color de $p_i$ o del de $k$, es decir de uno de los $10$ o de uno de los $10$ (por hipótesis inductiva).
Ahora, sea sin pérdida de generalidad $p_1$ el primo con el mismo color que $p_1\times p_2\times ...\times p_{10}$. Supongamos que hay un múltiplo $a$ de $p_1$ con distinto color que $p_1$, sin pérdida de generalidad del mismo que $p_2$. Luego $p_1\mid a$ y $p_2\mid p_1\times p_2\times ...\times p_{10}$, lo que contradice la condición c). Luego $p_1$ tendrá todos sus múltiplos de su color como buscábamos.