Will these frogs ever meet?

Question

Two frogs are on an eternal stairway. Will they ever be able to meet?

Anton is on step 14 and jumps 4 steps. Billy is on step 16 and jumps 6 steps.

The way I look at this is that as long as they're not on the same step, the one on the lowest jumps next, so:

• Their difference (Anton-Billy) is -2
• Anton jumps to step 18, difference = 2
• Billy jumps to step 22, difference = -4
• Anton jumps to step 22 - THEY MEET

If Anton had been on step 15 instead:

• Their difference is -1
• Anton jumps to step 19, difference is 3
• Billy jumps to step 22, difference is -3
• Anton jumps to step 23, difference is -1
• Since the difference has repeated, they will never meet

However, I am certain there's a much better way to find out if and where they will ever meet in a single equation.

Answer 1

In the very general case, suppose Anton starts on step $a_0$ and jumps by $a$ steps each time. Similarly, suppose Billy starts on step $b_0$ and jumps by $b$ each time. Let $n$ denote the number of jumps made by Anton, and $m$ the number of jumps made by Billy.

Then, we are trying to ask if the equation

$$a_0 + an = b_0 + bm$$

has a solution, for variables $n, m$ and constants $a_0,a,b_0,b$. Rewrite this equality as

$$an - bm = b_0 - a_0$$

This is a linear Diophantine equation in two variables. It is well-known that this has solutions if and only if $\gcd(a, b)$ divides $b_0 - a_0$ (see e.g. this math.se post), and thus the frogs can meet if and only if the difference in their starting positions is divisible by the greatest common divisor of their step distances.

---

For your specific instance, we have $a=4$ and $b=6$, whereby $\gcd(a,b)=2$. Thus, Anton and Billy meet only if the difference between their starting steps is even.

Answer 2

Stated formally the question is as follows:

Are there any natural numbers M,N such that:

14N + 4 = 16M + 6 ?

This is same as

7N = 1 + 8M

This means 7N has to give remainder 1 when divided by 8.
This only happens when N has the form: N = 8L + 7, where L is integer >= 0.
You can find this out directly by trying all remainders.

Now the last equation becomes:

7.8.L + 49 = 1 + 8M
56.L + 48 = 8M
7L + 6 = M

Now, when we summarize what we got so far,
we see that the frogs meet for all numbers N, M
such that: N = 8L + 7, M = 7L + 6 (where L = 0, 1, 2, 3, 4, ...).

Answer 3

There is! Let $n$ and $m$ be integers corresponding to the jumps of the frogs. Let $x$ and $y$ be the initial positions. Now if we are seeing if we can make two frogs equal, we are checking to see if we can write $x+ni=y+m=j$ for integers $i, j$, so we are asking if $x-y=(mi-nj)$. The term on the right is a multiple of the greatest common denominator of $n$ and $m$, so that $x-y=kgcd(n, m)$, so that conidition is that $gcd(n, m)|(x-y)$.

Answer 4

Stated formally the question is as follows:

Are there any non-negative integer numbers M,N such that:

14 + 4N = 16 + 6M ?

This is same as

2N = 1 + 3M

This means 2N has to give remainder 1 when divided by 3.
This only happens when N has the form: N = 3L + 2, where L is integer >= 0.
You can find this out directly by trying (for N) all remainders modulo 3.
Since 2 and 3 are co-prime, you get only 1 solution here, only 1 remainder modulo 3 which works.

Now the last equation becomes:

2.3.L + 4 = 1 + 3M
6.L + 3 = 3M
2L + 1 = M

Now, when we summarize what we got so far,
we see that the frogs meet for all numbers N, M
such that: N = 3L + 2, M = 2L + 1 (where L = 0, 1, 2, 3, 4, ...).

Answer 5

It is trivial to prove that they always meet if they start in the same step. If they don't :
Let :
$x$ = step at which the frog which starts lower starts
$m$ = nº of steps the frog wich starts lower jumps each time
$y$ = step at which the other frog starts
$n$ = nº of steps the other frog jumps each time
$Z$ = $(y-x)$ modulo $n$
$D$ = maximal common divisor of $m$, $n$ and $Z$
The frogs meet if and only if $\frac{m}D$ and $\frac{n}D$ are coprimes.

Proof:

The question is asking if there exist two non-negative integers $i$ and $j$ such that this equation (1) is satisfied : $$x+mi = y+nj$$ This is equivalent to (2) :
$$mi = (y-x) + nj$$

Let's define Z as (y-x) modulo n:
Equation (2) is equivalent to (3): $$mi = Z + nj$$ It is trivial to prove the equivalence if $(y-x)<n$ since $(A\pmod{B}=A)$ when $A<B$ and both are positive.
If $(y-x)>=n$ we may rewrite (2) as (4):
$$mi=(Z+nk)+nj=Z+n(k+j)$$ With k being an integer such that $(Z+nk)=(y-x)$. And now we are looking for integers $i$ and $(k+j)$ which satisfy the equation, which is no different than looking for integers $i$ and $j$. Thus we have proved that (2) is equivalent to (3) in all cases.
Let $D$ be the maximal common divisor of $m$, $n$ and $Z$. Equation (3) is equivalent to (5): $$\frac{m}Di=\frac{Z}D+\frac{n}Dj$$ If $\frac{m}D$ and $\frac{n}D$ are not coprime :
In such case there is a divisor $E$ greater than 1 for both $\frac{m}D$ and $\frac{n}D$. But E is not a divisor of $\frac{Z}D$, otherwise D could not be the mcd of $m$, $Z$ and $n$. This means that $\frac{m}Di$ and $\frac{n}Dj$ will be multiples of E for all values of $i$ and $j$. Rewriting (5) as (6) we have : $$\frac{m}Di-\frac{n}Dj=\frac{Z}D$$ Implying that a multiple of $E$ is equal to a non-multiple of $E$, which is not possible. Thus if $\frac{m}D$ and $\frac{n}D$ are not coprime the equation can't be satisfied (the frogs will never meet)

If $\frac{m}D$ and $\frac{n}D$ are coprime :
Let's rewrite (5) as (7):
$$Ai=C-Bj$$
Since $A$ and $B$ are coprime, from Bézout's identity we know that there exist integers $p$ and $q$ such that (8):
$$Ap + Bq = 1$$ (8) is equivalent to (9) :
$$Ap = 1 - Bq$$ (9) is equivalent to (10) : $$ACp = C - BCq$$ Thus we have proved that (7) can be satisfied with $i=Cp$ and $j=Cq$ when $\frac{m}D$ and $\frac{n}D$ are coprime

Answer 6

jump to ten. This answer would have been more concise but for the character count.