Research in Scientific Computing in Undergraduate Education

Lonely runner problem

Suppose k runners run, each with constant, but different, speed around a circular track of circumference 1.  For each runner, is there a time at which that runner is at least \frac{1}{k} from the other runners, as measured along the track?

This is known to be true for k\leq 7.

The problem is related to number theory problems of Diophantine approximation; see Bohman et al (2001) and Renault (2004), below. In this context the lonely runner problem was originally formulated in the following way (here the runners’ speeds are all taken to be integers, and a designated runner is assumed to have speed 0):

Given positive integers v_1, . . . , v_{k-1}, is  there a real number t such that:
\frac{1}{k} \leq\{tv_i\}\leq \frac{k-1}{k} \textrm{ for } 1\leq i \leq k-1 ?.

Here, \{x\} := x -\textrm{Floor}[x] is the fractional part of the real number x.

Could some insight as to a possible counterexample be obtained from computation?

Alternatively, can we try to use computation to get insight into the density of  times t for which there is a specified lonely runner?

For example, the following Mathematica® code:

Needs[“LinearRegression`”];
integerbound = 2000;
k = 8;
T = Sort[Table[RandomInteger[{1, integerbound}], {i, 1, k – 1}]]
timebound = 1000;
lonelytimes = {};
howmany = 1000;
Do[
t = RandomReal[{0, timebound}];
A = Table[FractionalPart[t*T[[i]]], {i, 1, k – 1}];
If[And[1/k <= Min[A], Max[A] <= (k – 1)/k],
lonelytimes = {lonelytimes, t}, lonelytimes = lonelytimes],
{j, 1, howmany}]
lonelytimes = Sort[Flatten[lonelytimes]];
Print[“Proportion t = “, N[Length[lonelytimes]/howmany]*100, “%”]
ListPlot[lonelytimes]
Regress[lonelytimes, x, x]

produces 7 random positive integers v_1, \ldots, v_7 in the range  [1,2000] and finds the percentage of times t, for 1000 uniformly random samples with 0 < t < 1000, for which \frac{1}{7}\leq tv_1\ldots, tv_7\leq \frac{6}{7}.

A sample run gave:

Integer set ={41, 754, 850, 984, 1056, 1250, 1541}

Proportion t = 12.3%

The sorted list of t values was almost linear with rank:

meaning that the t values obtained were approximately uniformly spread over the interval (0,1000).

References & reading

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: