# Kangaroo Coordinates

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?

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.

• In particular, Kangaroo can reach $6/\pi^2 \approx 61\%$ of all points. May 1 at 17:52
• @isaacg Yes, nice observation! The probability of a randomly chosen coordinate $(x, y)$ being visited by Kangaroo is exactly $\frac{6}{\pi^2}$. This is the same probability of two randomly chosen integers being coprime. May 3 at 7:20