7
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. That was a good explanation. Knowing now that they will meet, is there a quick way to determine where they meet, or is that explained in the link you included? $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 19:37
  • 1
    $\begingroup$ Yes, you can solve the Diophantine equation using that link (it isn't difficult math). You get an infinite number of solutions, and can pick any solution that you like. $\endgroup$ – nneonneo Oct 26 '15 at 19:38
  • $\begingroup$ Thank you. Much appreciated. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 19:47
  • $\begingroup$ Having some issues getting my brain wrapped around this. Would you be willing to give an example of how to use that to get to the first step (10) where Anton and Billy would meet if they started at a0 (2) and b0 (4)? Thanks again! $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 20:03
  • $\begingroup$ FYI, a quick way to see that in the Anton starts on 15 example that they never meet, simply note that Anton will always be on an odd step, and Billy will always be on an even one. This is a consequence of nneonneo's last statement, but is more easily seen. $\endgroup$ – Paul Sinclair Oct 26 '15 at 22:45
6
$\begingroup$

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, ...).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Still not sure I understand your explanation, but thanks for helping. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 16:35
1
$\begingroup$

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, ...).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think you made a mistake. Wouldn't it be: 14N - 16M = 2 7N - 8M = 1 $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 15:57
  • $\begingroup$ @OleDrewsJensen Yes, I was just chasing it too :) I just found it. Thanks. $\endgroup$ – peter.petrov Oct 26 '15 at 16:00
  • $\begingroup$ I see you edited it, so ignore my last, but not sure I understand the edited version... :-) Let me study it for a minute. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 16:00
  • $\begingroup$ My whole calculation is messed up. I was solving a different problem: A is on step 4 and jumps 14 steps, B is on step 6 and jumps 16 steps. Should I edit it for the real problem? The real is much simpler. $\endgroup$ – peter.petrov Oct 26 '15 at 16:06
  • $\begingroup$ So the only way I can solve this, is by trying all remainders? Thanks. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 16:09
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Not sure about ni and mi, as i is different from n and m. x had to "jump" 4 twice, and y had to "jump" only once, before they both met at 22. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 15:55
  • $\begingroup$ Since the jumps may or may not be the same, I assume we'll have to look at the jumps as i and j (as you actually mentioned in your reply). So it would look something like: x-y = m^j-n^i Not sure where to go with that, but thanks again for your post. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 16:40
  • $\begingroup$ You are right! I misunderstood your question. Not it is less elementary, but the solution has been edited $\endgroup$ – Max Chan Oct 26 '15 at 19:18
  • $\begingroup$ Thanks, that makes more sense, and looks similar to the link about linear Diophantine equation in another answer above. My only problem is that I have not (yet) been able to understand how to get the first step where they meet. $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 19:59
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for that answer. My head hurts now. :-) I am not looking for a proof, only a way to check if they will meet, which I have found from previous answers. I am now looking for the first (smallest number) step where they will meet, but as far as I can see (I still haven't grasped all the answers yet), the methods posted finds multiple steps where they meet, and I'll have to "dig around" to find the first (smallest). $\endgroup$ – Ole Drews Jensen Oct 26 '15 at 20:31
  • $\begingroup$ What is the minimun number of steps required to make the frogs meet should be handled in a different question. $\endgroup$ – Anonymous Coward Oct 26 '15 at 23:38
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks :-) I did know that. :-) Was hoping for something that would find the first (lowest) step on much larger numbers too. $\endgroup$ – Ole Drews Jensen Oct 27 '15 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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