Invisible runners in finite fields |
| |
Authors: | Sebastian Czerwiński |
| |
Affiliation: | a Faculty of Mathematics, Computer Science, and Econometrics, University of Zielona Góra, 65-516 Zielona Góra, Poland b Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, 30-387 Kraków, Poland |
| |
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. |
| |
Keywords: | Combinatorial problems Integer distance graphs The lonely runner problem |
本文献已被 ScienceDirect 等数据库收录! |
|