Thursday, August 8, 2019

Proving the Lonely Runner Problem Discretely

The other day I came across the Lonely Runner Conjecture from Tamás Görbe's tweet. Here's my attempt at an outline of a proof. In fact, I'm attempting a stronger result that is hinted by Czerwiński, S. (2012). "Random runners are very lonely". Journal of Combinatorial Theory, Series A. 119: 1194–1199 (arXiv.org)


Addenda:
August 12, 2019
This article contains numerous errors. Here's an update.


August 10, 2019
This is wrong. I know why it's wrong, but don't why it's wrong [sic]. I'll post an update





Consider the discrete [re]formulation of the problem where the runner's speeds take on distinct integral values and one of the runners stays still. We aim to prove

There exists a time t s.t. all the moving runners are exactly at a distance 1/2 from the still runner.

Now in addition to quantizing the speed of our runners, let us restrict t to discrete values also. In this view then, the circle consists of a ring of bins, and at each step (incrementing t by 1) each runner hops as many bins forward as their integral speed.

(Observe in the original formulation of the problem, we are free to scale t (as in to whatever units) as we wish. Thus it is important to keep in mind that it is only the relative magnitudes of the speeds of the runners that matters.)

Let us have N = pi bins in the ring where the pi's in the product are the distinct integral values of the runners' speeds. (It makes the argument seem clearer if you think of these pi's as co-prime, but our argument here doesn't hinge on it.)

Label the bins in the ring with numerals, starting with 0 (zero) for the starting bin (whence the race began). At any given time t, the bin bi for the i'th runner with speed pi is given by

bi = tpi  mod N

The runners then meet at bin 0 the starting point every N steps. Without loss of generality, assume N is divisible by 2. (There are multiple ways we can transform the case where N is odd, to an even one--but conceptually the simplest way is to just throw in another runner with speed 2.)

Now consider modulo N/2. Notice the runners also meet at bin N/2 at every time t = N(k+1/2)  (for all k in Z). Thus, the distance to the still runner at such times, after normalizing the ring's length to 1 is 1/2.

Also, note not all runners need to be running in the same direction for this result to hold. (Which in turn means the result holds from any runner's perspective.)

So this gives exact solutions for distance 1/2 as

t =  (k + 1/2)pi ,  k any integer
Note, at this point, t can be loosened to taken on fractional values.
~

What do you think? (This seems too easy. I must be missing something.)

No comments: