Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Los números pares tienen que ser necesariamente azules ya que se obtienen como suma de un número (su mitad) consigo mismo. Por tanto, si un número impar $2k+1$ está pintado de azul, se tiene que todos los siguientes impares $2k+3=(2k+1)+2$, $2k+5=(2k+1)+4$,... también tienen que estar pintados azules. Nos quedan, en consecuencia, las siguientes coloraciones:

• Todos los pares de azul y todos los impares de rojo.
• Todos los enteros de azul salvo los primeros $n$ impares, que están pintados de rojo, para cierto $n\geq 0$. En particular, para $n=0$, tendríamos todos los enteros pintados de azul.

Es fácil ver que estas dos formas de pintar cumplen la regla de coloración, luego son las únicas posibilidades.

Solución. Llamemos (1) al reemplazo $k\mapsto 3k-1$, (2) al reemplazo $k\mapsto 2k+1$ y (3) al reemplazo $k\mapsto\frac{k}{2}$. Observemos las siguientes cadenas de reemplazos válidas para cualquier entero $m\geq 0$ (es decir, distinguimos casos dependiendo del resto módulo $4$): \begin{align*} 4m&\stackrel{(3)}{\longmapsto}2m,\\ 4m+1&\stackrel{(2)}{\longmapsto}8m+3\stackrel{(1)}{\longmapsto}24m+8\stackrel{(1)}{\longmapsto}12m+4\stackrel{(1)}{\longmapsto}6m+2\stackrel{(1)}{\longmapsto}3m+1,\\ 4m+2&\stackrel{(1)}{\longmapsto}2m+1,\\ 4m+3&\stackrel{(1)}{\longmapsto}12m+8\stackrel{(1)}{\longmapsto}6m+4\stackrel{(3)}{\longmapsto}3m+2. \end{align*} Todas estas transformaciones acaban con un número estrictamente menor que el inicial salvo si empezamos con el $1=4\cdot 0+1$, caso en el que acabamos con el propio $1$. De este modo, aplicando reiteradamente estas cadenas de reemplazos podemos empezar en cualquier número $n$ y terminar en el $1$.

El resto de la demostración será ver que empezando por $1$ podemos multiplicar por $3$ sucesivamente para conseguir cualquier potencia de $3$. Esto es consecuencia de la siguiente cadena de reemplazos: \[3^a\stackrel{(1)}{\longmapsto}3^{a+1}-1\stackrel{(3)}{\longmapsto}\frac{3^{a+1}-1}{2}\stackrel{(2)}{\longmapsto}3^{a+1},\] donde la fracción es realmente un número entero ya que $3^{n+1}-1$ es par. Por lo tanto, podemos empezar en $1=3^0$ y pasar sucesivamente a $3^1,3^2,3^3,\ldots$ hasta llegar a $3^{2023}$.