Article ID Journal Published Year Pages File Type
429173 Information Processing Letters 2008 4 Pages PDF
Abstract

Suppose k runners having different constant speeds run laps on a circular track of unit length. The Lonely Runner Conjecture states that, sooner or later, any given runner is at distance at least 1/k from all the other runners. We prove here that the statement of the conjecture holds if we eliminate only one chosen runner. The proof uses a simple double-counting argument in the setting of finite fields. We also demonstrate that the original problem reduces to an analogous statement in particular ring Zn, where n is the sum of speeds of two distinct runners. In consequence we obtain a simple computational procedure for verifying the conjecture for any given set of integer speeds. Finally we derive some simple consequences of our results for coloring integer distance graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics