Checking that two numbers incremented with different values will eventually have the same value

Question

The root of the question is from a hackerrank task but at the end it's a mathematical problem which I don't understand. So the idea is that you have two kangaroos one starting from position x1 and the other starting from position x2. We know for sure that x2 > x1. The question is, given that the length of the jump of the first kangaroo is v1 and the second is v2 will the kangaroos eventually be at the same spot at the same time. My approach was to increment both x1 and x2 until they became equal or x1 gets greater than x2 which logically works but turns out to be a slower solution. After that I've checked other solutions and it turned out that this check:

(x2 - x1) % (v1 - v2) == 0

actually is enough. If the modulus is equal to zero then they'll meet, otherwise - they won't. I would appreciate if someone explains in more details why this actually works.

Answer 1

We can write the positions of the kangaroos as a function of time, which I'll call $p_1(t)$ and $p_2(t)$. Note $t$ here is the number of time steps, which must be an integer. At each time step, kangaroo 1 moves by a distance $v_1$, so after $t$ steps, it has moved a distance $t\ v_1$. This gives us a simple linear equation for each kangaroo:

$$p_1(t) = x_1 + v_1 t$$

$$p_2(t) = x_2 + v_2 t$$

To determine if they meet, we need to find an integer $t$ such that $p_1(t) = p_2(t)$. This equation can be easily solved algebraically without imposing the limitation that $t$ be an integer:

$$x_1 + v_1 t = x_2 + v_2 t$$

$$v_1 t - v_2 t = x_2 - x_1$$

$$t = \frac{x_2 - x_1}{v_1 - v_2}$$

This will find the real solution for $t$, provided it exists. In order for this solution to be an integer, $x_2 - x_1$ must be divisible by $v_1 - v_2$. There are a number of ways of checking this condition; one simple one is to check that the remainder of the division is zero, which can be expressed as $(x_2 - x_1) \% (v_1 - v_2) = 0$, since $a\%b$ is by definition the remainder of $\frac ab$.

Note that this includes negative solutions for $t$; If we want to exclude these, we need to check that $v_1 > v_2$, which assures that the first kangaroo will eventually catch up.

Answer 2

The kangaroos will meet if and only if there exists $t$ such that $x_1+tv_1 = x_2+tv_2$, which means that $x_1-x_2=t(v_2-v_1)$, which means that $x_2-x_1 = 0 [v_1-v_2]$.

Answer 3

We actually need the added condition that $v_1>v_2$, along with the modulus being zero.

The kangaroos will eventually be at the same point if there exists a natural number $n$ such that $$x_1+nv_1=x_2+nv_2$$ Assuming such $n$ exists, then it must be equal to $$n = \frac{x_2-x_1}{v_1-v_2}$$ So we can see that $x_2-x_1$ must be a multiple of $v_1-v_2$. Further, since $c_2-x_1>0$, we have that $v_1-v_2>0$. Conversely, if this ratio is an integer and if $v_1>v_2$, then we can see that the first equation is solved for some positive $n$, and so the kangaroos meet.