کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429173 687071 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Invisible runners in finite fields
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Invisible runners in finite fields
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 2, 30 September 2008, Pages 64-67