The Lonely Runner Cojecture
Download
Report
Transcript The Lonely Runner Cojecture
The Lonely Runner Cojecture
Jason Holman
Areas
Number Theory
Diophantine Equations
Graph Theory
Open questions in this area
Traces of combinatorics
Logic
History of the Problem
JorgWills first discovered the problem in 1967
Thomas Cusick found it independently
Given a name by Luis Goddyn
What is it?
In a mathematical sense, it is the following equation
In a general sense, it says that if “runners” are running on a
track of unit length at distinct speeds, every runner will at
some point be
from all other runners at some point
http://en.wikipedia.org/wiki/Lonely_runner_conjecture
This is something that seems to be quite obvious, yet shows
to be very difficult to prove
Proofs of Cases So Far
k=1 is a trivial case
k=2 is a trivial case
k=3 is said to be included in all cases greater than 3
k=4 was proven in the 1970’s by Betke and Wills
k=5 was proven in the 1980’s by Cusick and Pomerance.
This required computer checking
Bienia and others gave a simpler proof for this case in the 1990’s
k=6 was proven by Bohman, Holzman, and Kleitman in 2001
A simpler proof of this case was given by Renault in 2004
k=7 was proven in 2008 by Barajas and Serra
Open Problem
The conjecture has been proven for cases up to k=7
Cases where k is greater than 7 or a general proof have not
yet been found
There does not appear to be a certain way to “attack” this
proof
PDF of proofs
3 and 5 five runners have similar proofs
The rest are quite different and very in depth
Sources
http://blogs.ams.org/mathgradblog/2013/08/22/lonely-
runner-conjecture/
http://rjlipton.wordpress.com/2012/01/28/the-lonelyrunner-conjecture/
http://stathletics.tumblr.com/post/21662762724/thelonely-runner-conjecture
Barajas, Serra. The lonely runner with seven runners. 2008