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

Si denotamos por $(x_t(n),y_t(n))$ y $(x_m(n),y_m(n))$ a las posiciones de las naves terrestre y marciana, respectivamente, después de su $n$-ésimo movimiento, el problema se reduce a demostrar que existe $n$ tal que $x_t(n)=x_m(n)$ y $y_t(n)=y_m(n)$ independientemente del valor de las posiciones iniciales $(x_t(0),y_t(0))$ y $(x_m(0),y_m(0))$. No obstante, con la estrategia propuesta, si la nave marciana elige la velocidad $(h,v)$ en su $n$-ésimo movimiento, se cumplirá que \begin{eqnarray*} x_t(n)-x_m(n)&\equiv x_t(n-1)+(h+1)-x_t(n-1)-h = x_t(n-1)-x_t(n-1)+1\, (\text{mód}\ 2000),\\ y_t(n)-y_m(n)&\equiv y_t(n-1)+(v+1)-y_t(n-1)-v = y_t(n-1)-y_t(n-1)+1\, (\text{mód}\ 2001). \end{eqnarray*} Como cada una de estas diferencias se va incrementando en una unidad a cada movimiento, deducimos que $x_t(n)-x_m(n)=x_t(0)-x_m(0)+n\, (\text{mód}\ 2000)$ y $y_t(n)-y_m(n)=y_t(0)-y_m(0)+n\, (\text{mód}\ 2001)$ para todo $n$. Por lo tanto, el problema se reduce a la existencia de un número natural $n$ que sea solución del siguiente sistema de ecuaciones en congruencias: \[\begin{cases}n\equiv -x_t(0)+x_m(0)\, (\text{mód}\ 2000),\\ n\equiv -y_t(0)+y_m(0)\, (\text{mód}\ 2001).\end{cases}\] Como $2000$ y $2001$ son primos entre sí, el teorema chino del resto nos asegura que este sistema siempre tiene solución (única módulo $2000\cdot 2001$), luego la nave terrestre siempre alcanzará a la marciana.