首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号