Kangaroo Coordinates

Question

A kangaroo is sitting at the coordinate (1, 1). If the kangaroo is at some coordinate (a, b), it can always jump to (a + b, b) or to (a, a + b). Which positive integer coordinates can the kangaroo not jump to?

Answer 1

Kangaroo cannot jump to coordinates $(x, y)$ where:

$gcd(x, y) > 1$, where $gcd$ denotes the greatest common divisor

This is simply because:

$gcd$ is invariant under the given transformation

$gcd (a + b, b) = gcd (a, a + b) = gcd (a, b)$, and initially $gcd (1, 1) = 1$

The Kangaroo can reach any positive $(x, y)$ where $gcd (x, y) = 1$.

To reach any positive $(x, y)$ where $gcd (x, y) = 1$, the kangaroo can: Backtrack the previous coordinate point by subtracting smaller coordinate from the larger one (note that both coordinates cannot be equal after the initial state) until it reaches $(1, 1)$. Then it can traverse in the reverse order.

Example, to reach $(8, 5)$, Kangaroo can first analyze this:

$(8, 5)$ -> $(3, 5)$ -> $(3, 2)$ -> $(1, 2)$ -> $(1, 1)$

It is always possible to reach $(1, 1)$ while backtracking, because:

We can always make one of the coordinates equal to $1$ (i.e. $gcd$).

$($Larger, Smaller$)$ = $($Dividend, Divisor$)$ ---> $($Remainder, Divisor$)$ ... after subtracting Divisor from Dividend exactly Quotient number of times. This is basically the Euclid's Division Algorithm and guarantees that the final remainder would be the $gcd$ of the initials.

Note that if one of the coordinates becomes $1$, the other (say $x$) can be made $1$ by subtracting $1$ from it $x-1$ times.

Some plots in Mathematica: Observe that there are more green points than red! Kangaroo is lucky.