17
$\begingroup$

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?

$\endgroup$

1 Answer 1

21
$\begingroup$

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: Mathematica Plots Observe that there are more green points than red! Kangaroo is lucky.

$\endgroup$
2
  • 5
    $\begingroup$ In particular, Kangaroo can reach $6/\pi^2 \approx 61\%$ of all points. $\endgroup$
    – isaacg
    May 1, 2023 at 17:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – thisIs4d
    May 3, 2023 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.