I was working on some coding related to this topic I found on Stack Overflow. This lead me to a math problem I thought would be interesting. I was wondering if one was given a starting point, what points could the robot reach. For instance, if the robot started at $(10,15)$, which coordinates would be reachable. To restate the problem,
A robot moves in the following way. If it is at the point $(x,y)$, it can move to either $(x+y,y)$ or $(x,x+y)$. If the robot starts at the point $(10,15)$, what points are reachable in a finite number of moves?
I noticed that each move preserves the greatest common divisor of the two coordinates, so all the coordinates that are reachable must have gcd equal to 5. Moreover, for relatively prime integers $a$ and $b$, if the robot can move from $(a,b)$ to $(c,d)$, then it can move from $(na, nb)$ to $(nc, nd)$. Therefore, we just have to consider the coordinates that are reachable from $(2,3)$ and just multiply each coordinate by 5. However, I'm not sure what coordinates are reachable. There are coordinates like $(35, 75)$ which are not reachable, even though their greatest common divisor is 5. Any help on the question would be great. Thanks!
Premise
This answer aims to give a intuition of the solution, without going too mush into detail and leaving some demonstrations to the reader.
Hypotesis
I assume the robot can only move in points with positive coordinates.
Solution
History of a position
Given a starting point $(x, y)$:
Considered that, every position on the first quadrant (excluding the diagonal) has a unique previous position. Let us define:
$ \begin{equation} P^{-1}(x,y) = \begin{cases} (x - y, y) & \mbox{if } x > y,\\ (x, y - x) & \mbox{if } x < y,\\ (x, y) & \mbox{if } x = y.\\ \end{cases} \end{equation} $
By repeatedly computing the previous position, we can determine the whole history $H(x, y)$ of the moves made by the robot to reach the current position.
$ \begin{equation} H(x_0,y_0) = \{(x, y) \colon\ (x, y) = P^{-n}(x_0, y_0) \text{ for some } n \in \mathbb{N} \}, \end{equation} $
where $P^{-n} = P^{-1} \circ P^{-1} \circ \cdots \circ P^{-1}$.
So, every point in this space encodes the whole history of moves needed for reaching it. In fact, by repeatedly subtracting $|x-y|$ from the maximum of the two coordinates, we can go backwards until reaching some element on the diagonal.
Future of a position
The previous considerations lead us to the following statement: one position $(x_1, y_1)$ can be reached from another position $(x_0, y_0)$ if and only if $H(x_1, y_1) \supseteq H(x_0, y_0)$. As a consequence, the set of all positions reachable from position $(x_0, y_0)$ with a finite number of moves is the set
$ \begin{equation} F(x_0,y_0) = \{(x, y) \colon\ H(x, y) \supseteq H(x_0, y_0) \}. \end{equation} $
Visual representation of results
I don't know if this set can be expressed in some more explicit form. We can have an idea of how this sets are made, by visualizing them. The maximal sets of reachable points are of the form $F(x, x)$.
By observing that
$ \begin{equation} F(n, n) = \{(nx, ny) \colon \ (x, y) \in F(1,1)\}, \end{equation} $
we deduce that $F(x, x)$ are scaled versions of $F(1, 1)$, that is represented in white in the following image.
Note further that since all points on the first quadrant are reachable from a starting point on the diagonal and since no point on the diagonal is reachable from another point on the diagonal, the sets $F(x, x), x \in \mathbb{N}\setminus\{0\}$, do not intersect and their union is the whole set of positions. This property can be visualized in the following image where $F(1,1)$ is depicted in red, $F(2,2)$ in green and $F(3,3)$ in blue.