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

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}$.