On the lonely runner conjecture II


We consider (LRC) .

Conjecture Suppose n>1 runners having distinct constant integer speeds v_k start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than \frac{1}{n+1} from the origin.

We first show trivial proves for n=2,3 runners.

Let \| x \| denote the distance of x to the nearest integer.

Let \kappa_n = \inf \max \limits_{0 \leq t \leq 1} \min \limits_{ 1 \leq i \leq n} \| v_i t \|. where the infimum is taken over all n-tuples v_1, ... v_n of distinct positive integers.

In terms of \kappa_n the LRC state that \kappa_n= \frac{1}{n+1}

Without loss of generality (wlog) we can assume k < m \Leftrightarrow v_k < v_m .

Case n=2. Wlog we can assume v_1, v_2 are relatively prime. At time t_k= \frac{m}{v_1+v_2}, m=1..v_1+v_2-1 two runners are at the same distance from the origin from different sides of the lap at distances proportional to \frac{1}{v_1+v_2}. Since they are relatively prime both runners visit all the points \frac{m}{v_1+v_2}, m=1..v_1+v_2-1. The largest distance is \frac{ \left[ \frac{v_1+v_2}{2} \right] }{v_1+v_2}, where \left[ \circ \right] means integer part.

For example, v_1=1, v_2= 2, at times \frac{1}{3}, \frac{2}{3} runners are at positions (\frac{1}{3}, \frac{2}{3}) and (\frac{2}{3},\frac{1}{3}) and the maximum distance from origin is \frac{\left[ \frac{1+2}{2}\right]}{3}= \frac{\left[1.5 \right]}{3}= \frac{1}{3}.

Another example, v_1= 2, v_2= 3, the maximum distance is \frac{2}{5} > \frac{1}{3}.

If v_1, v_2 \mod 2 =1 the maximum distance is \frac{1}{2} >  \frac{1}{3} at time \frac{1}{2}.

In general the maximum distance is r_{1,2}= \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right) with the minimum for runners at speeds v_1= 1, v_2= 2. Therefore, \kappa_2= \frac{1}{3}.

Case n=3.

  • First we assume simple case: v_3 \mod ( v_1+v_2 )= 0, e.g v_3= q(v_1+v_2), q \in \mathbb{N}_+.

    At times t= \frac{m}{v_1+v_2} runner 3 is at the origin. There is a time such that some time before it was the same distance with runner 1 and some time after it will be the same distance with runner 2. (The situation is reversed at times 1-t). We are interested when that is happening for the time runners 1 and 2 are most distant from the origin.

    For runners 1 and 3: They need to pass r_{1,2} with speed v_1+v_3, so the time needed is \frac{r_{1,2} }{v_1+v_3}. Runner 3 passes r_{1, 3}= \frac{v_3 r_{1,2} }{v_1+v_3}= r_{1,2} \frac{1}{1+v_1 / v_3 }. Therefore, the closest point is reached when \frac{v_1}{v_3}= \frac{v_1}{t (v_1+v_2) } is maximum.

    r_{1, 3}=  \frac{q ( v_1+v_2 ) }{v_1+ q ( v_1+v_2 ) }  \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right)

    If (v_1+v_2) \mod 2 = 0, r_{2, 3} < r_{1, 3} around r_{1,2}= \frac{1}{2}

    r_{2, 3}=  \frac{1}{2} \frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) }

    Lemma 1. \frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) } > \frac{1}{2}.
    Proof. \frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) } - \frac{1}{2} = \frac{1}{2} \frac{ 2 q ( v_1+v_2 ) -  v_2 -  q ( v_1+v_2 )}{v_2+ q ( v_1+v_2 ) }  = \frac{1}{2} \frac{  q v_1  + ( q - 1) v_2 }{v_2+ q ( v_1+v_2 ) } > 0 \blacksquare

    Now, consider the case when (v_1+v_2) \mod 2 = 1.

    r_{1, 3}=  \frac{1}{2} \frac{q ( v_1+v_2 ) }{v_1+ q ( v_1+v_2 ) }   \frac{ v_1+v_2 - 1 }{ v_1+v_2}  =  \frac{1}{2} \frac{q ( v_1+v_2 - 1 ) }{v_1+ q ( v_1+v_2 ) }

    Lemma 2. \frac{q ( v_1+v_2 - 1 ) }{v_1+ q ( v_1+v_2 ) } \geq \frac{1}{2}
    Proof. \frac{ ( v_1+v_2 - 1 ) }{v_1/q + v_1+v_2 } - \frac{1}{2} = \frac{2 v_1+ 2 v_2 - 2 - v_1/q - v_1-v_2 }{2 \left[ v_1/ q+ ( v_1+v_2 ) \right] } = \frac{ v_1 \left( 1- \frac{1}{q} \right)+ v_2 - 2 }{2 \left[ v_1/ q+ ( v_1+v_2 ) \right] } . Since v_2 \geq 2 nominator is greater than 0, except when v_2=2, v_1= 1, q= 1 \blacksquare

    Corollary 3. r_{1, 3} \geq \frac{1}{4}.
    Corollary 4. r_{1, 3} = \frac{1}{4} only for v_1=1, v_2=2, v_3=3.

  • Case: v_3 \mod ( v_1+v_2 ) \neq 0.

    Lemma 5. Fix time t=  \frac{m}{v_1+v_2}, m \in \{1, ..., v_1+v_2-1 \} . Let r_3 be the distance from the origin of runner 3 at the moment t and r_{1,2} > r_3 be the distance of the runners 1 and 2 from the origin at the same time. The maximal distance when runners 1 and 2 or 1 and 3 equidistant around time t is greater than \frac{r_3+r_{1, 2}}{2}.
    Proof. Either the runner 3 is running toward or away from the origin. e.g. the distance to the origin either decrease with time or increase. Let v be the speed of the runner 1 or runner 2 moving in opposite direction, so that the difference in distances is decreasing moving either forward or backward in time. Since v_3 > v runner 3 will cover greater distance away from the origin that other runner \blacksquare

    Lemma 6. Fix the time t= \frac{m}{v_1+v_2} when r_{1,2}= \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right). Let r'_3= \frac{m v_3 \mod (v_1+v_2) }{v_1+v_2} , and r_3= \min (r'_3, 1-r'_3)= \| r'_3\| – distance of runner 3 from the origin. r_{1, 2} + r_3 > \frac{1}{2} .
    Proof. r_3 \geq \frac{1}{v_1+v_2}, r_{1,2}+r_3 \geq \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right) + \frac{1}{v_1+v_2} = \frac{1}{2} + \frac{2- (v_1+v_2) \mod 2 }{v_1+v_2} > \frac{1}{2} \blacksquare

    Combining Lemma 5 and Lemma 6 shows \max (r_{1,3}, r_{2,3}) > \frac{1}{4}.

Overall, \kappa_3= \frac{1}{4} only for runners v_1=1, v_2=2, v_3=3.

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to On the lonely runner conjecture II

  1. Pingback: On the lonely runner conjecture III | Crackpot Trisector Notes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s