Número mínimo de formas de colorear cada número entero

Question

He visto este problema flotando por ahí desde hace tiempo pero sin respuesta.

Ya que el plazo de USAMTS ha pasado, me gustaría ver una respuesta para esto. Lo más lejos que llegué con esto fue que $n \geq 4$ (se ha demostrado que debe haber más de $3$ ). Me inclino a decir que $4$ es la respuesta.

Encuentra el menor número entero positivo $n$ que satisfaga lo siguiente: Podemos colorear cada entero positivo con uno de $n$ colores tal que la ecuación $w+6x=2y+3z$ no tiene soluciones en números enteros positivos con todas las $w,x,y,z$ el mismo color. (Tenga en cuenta que $w,x,y,z$ no tienen por qué ser distintos: por ejemplo, 5 y 7 deben ser de distinto color porque $(w,x,y,z)=(5,5,7,7)$ es una solución a la ecuación anterior.

Answer 1

Mi solución completa que ojalá obtenga un 5.

---

$$\begin {eqnarray} w + 6x &=& 2y + 3z \qquad (1) \end {eqnarray}$$

En primer lugar, demostramos que $n \ge 4$ .

Lema : Para cualquier número entero positivo $m$ los enteros $m$ , $2m$ y $3m$ deben tener colores distintos por pares.

Prueba : Obsérvese que, para cualquier número entero positivo $m$ se cumplen las siguientes afirmaciones.

• El cuádruple ordenado $(w,x,y,z)=(2m,m,m,2m)$ satisface (1), por lo que $m$ y $2m$ no pueden tener el mismo color.
• El cuádruple ordenado $(w,x,y,z)=(3m,m,3m,m)$ satisface (1), por lo que $m$ y $3m$ no pueden tener el mismo color.
• El cuádruple ordenado $(w,x,y,z)=(3m,2m,3m,3m)$ satisface (1), por lo que $2m$ y $3m$ no pueden tener el mismo color.

Por lo tanto, $m$ , $2m$ y $3m$ deben tener todos colores diferentes. $\Box$

Por el lema 1, $n \ge 3$ . Ahora, digamos, para no contradecir, que $n=3$ es suficiente. Que el color del entero positivo $u$ sea $c(u)$ . Entonces, digamos que $c(m)=r$ , $c(2m)=s$ y $c(3m)=t$ , donde $r$ , $s$ y $t$ son distintos por parejas. Entonces, por el lema 1, tenemos que $c(6m) \ne c(2m)$ y $c(6m) \ne c(3m)$ Así que $c(6m) = c(m) = r$ . Esto también da $c(12m) = c(2m)$ sustituyendo $m \mapsto 2m$ en la ecuación $c(6m) = c(m)$ . Y $c(2m) = s$ Así que $c(12m) = s$ .

Lema : Para cualquier número entero positivo $m$ los enteros $2m$ , $9m$ y $12m$ no pueden tener todos el mismo color.

Prueba : Obsérvese que, para cualquier número entero positivo $m$ el cuádruple ordenado $(w,x,y,z)=(12m,2m,9m,2m)$ satisface (1), por lo que $2m$ , $9m$ y $12m$ no pueden tener todos el mismo color.

Por el lema 2, y el hecho de que $c(2m)=c(12m)=s$ tenemos $c(9m)\ne s$ . Por el lema 1, $c(9m)\ne c(3m)$ Así que $c(9m) \ne t$ . Por lo tanto, $c(9m)=r$ . Pero, por el lema $1$ sustituyendo $6m$ y $9m$ no pueden tener el mismo color, por lo que tenemos una contradicción con el hecho de que $n=3$ colores es suficiente. Por lo tanto, $n \ge 4$ .

Ahora, afirmamos que la siguiente construcción para $n=4$ los colores funcionan:

• Colorea el entero positivo $a$ $\textbf{red}$ si y sólo si $\nu_3 (a)$ es par y $\frac {a}{3^{\nu_3(a)}} \equiv 1 \pmod {3}$ .
• Colorea el entero positivo $a$ $\textbf{blue}$ si y sólo si $\nu_3 (a)$ es par y $\frac {a}{3^{\nu_3(a)}} \equiv 2 \pmod {3}$ .
• Colorea el entero positivo $a$ $\textbf{green}$ si y sólo si $\nu_3 (a)$ es impar y $\frac {a}{3^{\nu_3(a)}} \equiv 1 \pmod {3}$ .
• Colorea el entero positivo $a$ $\textbf{yellow}$ si y sólo si $\nu_3 (a)$ es impar y $\frac {a}{3^{\nu_3(a)}} \equiv 2 \pmod {3}$ .

Aquí, $v_3(r)$ representa el mayor número entero positivo $k$ tal que $3^k \mid r$ .

Para demostrar que esta construcción es una coloración válida, supongamos primero, en aras de la contradicción, que tenemos un cuádruple $(w,x,y,z)$ tal que $w$ , $x$ , $y$ y $z$ todos poseen el mismo color.

Considere el cuádruple $\left( \frac {w}{k}, \frac {x}{k}, \frac {y}{k}, \frac {z}{k} \right)$ , donde $k = 3^{\text{min} \left( \nu_3 (w), \nu_3(6x), \nu_3(y), \nu_3(3z) \right)}$ que también es igual a $$3^{\text{min} \left( \nu_3 (w), 1 + \nu_3 (x), \nu_3 (y), 1 + \nu_3 (z) \right)}.$$ Permitimos $x$ y $z$ para convertirse en racionales, ya que el denominador debe ser $1$ o $3$ , haciendo que $6x$ y $3z$ sigue siendo integral. Lo que hemos hecho es dividir $(w,x,y,z)$ un número de veces suficiente para que al menos uno de $\frac{w}{k}$ , $6\frac{x}{k}$ , $2\frac{y}{k}$ y $\frac{z}{k}$ no divisible por $3$ . Así que lo dividimos en dos casos.

• Si uno de $w$ y $2y$ no es divisible por $3$ , entonces el otro no está tan bien. Como $\nu_3 (6x)$ y $\nu_3 (3z)$ son ambos de la paridad opuesta a la de $\nu_3 (w)$ y $\nu_3 (y)$ , ambos $\nu_3 (6x)$ y $\nu_3 (3z)$ son impar y así $6x$ y $3z$ son ambos divisibles por $3$ . Por lo tanto, tomando ambos lados mod $3$ nos da $w \equiv 2y \pmod 3$ . Por lo tanto, ya que uno de $w$ o $2y$ no es divisible por $3$ el otro tampoco lo es, así que $w \equiv y \pmod 3$ . Esto no puede satisfacerse con $w \equiv 2y \pmod {3}$ y $w \not\equiv 0 \pmod 3$ Así que tenemos una contradicción.

• Si uno de $6x$ y $3z$ no es divisible por $3$ Entonces, el otro no es tan bueno. Dado que $\nu_3(x)$ y $\nu_3(2y)$ tienen paridad opuesta, deben ser divisibles por $3$ . Sea $x_1 = 3x$ y $z_1 = 3z$ . Entonces, $w + 2x_1 = 2y + z_ 1$ . Tomando mod 3, tenemos $2x_1 \equiv z_1 \pmod 3$ . Por lo tanto, uno de ellos no es divisible por 3, así que el otro tampoco lo es. Pero $x_1$ y $z_1$ son ambos factores de $x$ y $z$ y encontramos que $$x_1 \equiv z_1 \pmod 3,$$ lo cual es, de nuevo, una contradicción.

$$\blacksquare$$