# Number of distinct points at which runners meet.

Two persons are running on a circular track either in the same direction or in the opposite direction, indefinitely. The speed of both of them is given, say $u$ and $v$. Now, how do I find out the the number of distinct points at which they will meet on the circle.

-
Have you tried to solve this problem yourself? – Ben Millwood Aug 30 '12 at 18:41
Yeah, well the first meeting point is C/(v-u), considering the circumference is C and v>u. Now the meetings points are going to be multiples of this. So nC/(v-u) is going to be equal to some kC/(v-u). Since, the path is circular, I'm expecting n can be decomposed to something less than C using modulo, but I'm getting nowhere with this approach :| – n0nChun Aug 30 '12 at 18:45
Yeah, I've gotta say, the problem is slightly less straightforward than it looks... it would have saved me some time if you'd mentioned that you'd already tried the obvious approach :) – Ben Millwood Aug 30 '12 at 18:50

$\omega_A=\frac{v}{C/2}$ and $\omega_B = \frac{u}{C/2}$ will be the angular speeds. Say you have angular speeds $\omega_A$ and $\omega_B$, and initial angles $\theta_{A0}$ and $\theta_{B0}$, then A's angle on time $t$ is $\theta_A(t)=\theta_{A0}+\omega_At$ and B's angle on time $t$ is $\theta_B(t)=\theta_{B0}+\omega_B t$.

The meeting angles are the solutions of the equation

$\theta_A(t)=\theta_B(t) + n2\pi$ or $\theta_{B0}+\omega_B t=\theta_{A0}+\omega_At + n2\pi$ where $n$ is $a$ integer.

This gives solutions:

$t = (n2\pi +\theta_{A0}-\theta_{B0})/(\omega_B-\omega_A)$

(assuming $\omega_B \neq \omega_A$, which would mean they'd always or never meet)

substituting this in A's angle equation gives meeting angles:

$\theta_{A0} + \omega_A(n2\pi +\theta_{A0}-\theta_{B0})/(\omega_B-\omega_A) = \text{constant} + \frac{\omega_A}{(\omega_B-\omega_A)}n2\pi$

as you can see, if $\omega_A/(\omega_B-\omega_A)$ is not rational ($p/q$ where $p$ and $q$ are integers), then you will get infinite meeting points because you will never get multiples of $2\pi$ added to the constant. And note that $\omega_A/(\omega_B-\omega_A)$ is rational iff $\omega_A/\omega_B$ is rational, which happens iff $u/v$ is rational.

So basically, if the ratio between the speeds is not $a$ rational number, there will be infinite meeting points.

-

This problem becomes much easier if one uses the right units and the right coordinate system.

Let the runners be $A$ and $B$, and let $A$ be the slower runner. It’s convenient to measure distance in laps and time in $A$-laps, where one $A$-lap is the time it takes $A$ to run one lap. Consider first the case in which $A$ and $B$ circle the track in the same direction.

$B$’s speed is $v+1$ laps per $A$-lap for some $v>0$, so he gains $v$ laps on $A$ in each $A$-lap and passes $A$ at those times $t$ such that $vt$ is an integer. At time $t$ runner $A$ is at position $t-\lfloor t\rfloor$ on the track, having completed $\lfloor t\rfloor$ full laps. Thus, the runners meet at those points $t-\lfloor t\rfloor=t\bmod 1$ at which $vt$ is an integer.

Suppose first that $v$ is rational, say $v=m/n$ in lowest terms. Then $vt=k\in\Bbb Z$ iff $t=kn/m$, so the runners meet precisely at those times $t$ that are integral multiples of $n/m$. Since $m$ and $n$ are relatively prime, $\{kn\bmod m:k\in\Bbb Z^+\}=\{0,\dots,m-1\}$, so the set of meeting points is

$$\left\{\frac{kn}m-\left\lfloor\frac{kn}m\right\rfloor:k\in\Bbb Z^+\right\}=\left\{\frac{k}m:k=0,\dots,m-1\right\}\;,$$

and there are $m$ of them.

If $v$ is irrational, the set of meeting times is $\{kv^{-1}:k\in\Bbb Z^+\}$, and the set of meeting points is $\{kv^{-1}\bmod 1:k\in\Bbb Z^+\}$, which is well-known to be dense in $[0,1)$ and therefore infinite. Of course one can observe directly that the set is infinite: if it weren’t, we’d have $mv^{-1}=nv^{-1}+k$ for some positive integers $m,n$, and $k$, and then $v^{-1}=\frac{k}{m-n}$ would be rational.

Now suppose that $B$ runs in the opposite direction around the track at a speed $u$, not necessarily greater than $1$. Let $v=u+1$, his speed relative to $A$’s position, so they meet whenever $vt$ is an integer. As before $A$ is at position $t-\lfloor r\rfloor=t\bmod 1$ at time $t$, so the analysis proceeds exactly as before.

The algebra to convert to other units is routine. In particular, if $r$ is the ratio of $B$’s speed to $A$’s, $v=r-1$ when they’re running in the same direction and $r+1$ when they’re running in opposite directions.

-