# 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).