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.
Number of distinct points at which runners meet.
-
0Yeah, 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 :) – 2012-08-30
2 Answers
$\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.