In a board of $2000\times2001$ squares with integer coordinates $(x,y)$, $0\leq{x}\leq1999$ and $0\leq{y}\leq2000$. A ship in the table moves in the following way: before a move, the ship is in position $(x,y)$ and has a velocity of $(h,v)$ where $x,y,h,v$ are integers. The ship chooses new velocity $(h^\prime,v^\prime)$ such that $h^\prime-h,v^\prime-v\in\{-1,0,1\}$. The new position of the ship will be $(x^\prime,y^\prime)$ where $x^\prime$ is the remainder of the division of $x+h^\prime$ by $2000$ and $y^\prime$ is the remainder of the division of $y+v^\prime$ by $2001$. There are two ships on the board: The Martian ship and the Human trying to capture it. Initially each ship is in a different square and has velocity $(0,0)$. The Human is the first to move; thereafter they continue moving alternatively. Is there a strategy for the Human to capture the Martian, independent of the initial positions and the Martian’s moves? Note: The Human catches the Martian ship by reaching the same position as the Martian ship after the same move.
Problem
Source: Spanish Communities
Tags: analytic geometry, combinatorics unsolved, combinatorics
09.09.2020 19:09
The answer is yes, there is a strategy. Let $(x,y)$ and $(z,w)$ be the initial positions of the Human and Martian ships, respectively. The strategy is the following: $\bullet$ Choose an integer $K$ such that \begin{align*} K &\equiv x-z-1 \pmod{2000}\\ K &\equiv y-w-1 \pmod{2001} \end{align*}Such a $K$ exists by the Chinese Remainder Theorem. $\bullet$ The Human ship chooses velocity $(-1,-1)$ in the first turn. Thus, it moves to the position $(x-1\pmod{2000}, y-1 \pmod{2001})$ $\bullet$ From now on, if the Martian ship chooses velocity $(h_{i}, v_{i})$ in its $i$-th turn, the Human ship chooses velocity $(h_{i}-1,v_{i}-1)$ in the next turn. As velocities change by at most one, the Human ship can always do this. Now, if the Human ship performs that strategy, it will capture the Martian ship in its $(K+1)$-th turn, as the Human ship will be in the square $(x-1+h_{1}+h_{2}+...+h_{K}-K \pmod{2000}, y-1+v_{1}+v_{2}+...+v_{K}-K \pmod{2001})$ and the Martian ship would be at $(z+h_{1}+h_{2}+...+h_{K} \pmod{2000}, w+v_{1}+v_{2}+...+v_{K}\pmod{2001})$, but $$(x-1+h_{1}+h_{2}+...+h_{K}-K \pmod{2000}, y-1+v_{1}+v_{2}+...+v_{K}-K \pmod{2001})= (z+h_{1}+h_{2}+...+h_{K} \pmod{2000}, w+v_{1}+v_{2}+...+v_{K} \pmod{2001})$$We are done. $\square$