Open Problem Garden

The Following Proof is posted on arvix.com

Proof The runners’ set-off running at t = 0 from a common origin O.
Let us label the speeds of the n runners from slowest to fastest s1, s2, s3, ...sn, where the speeds are equivalent to distinct integers. Consider that we scale the length of the track up by a factor of s1 x s2 x s3 x s4 ....x s(n-1). This is equivalent to watching the events occur in a slower time frame. Clearly in this case, all runners coincide back at the starting point at the same time T, where T is the product of their speeds. We ask ourselves where is the nth runner at this time T.
The nth runner is either also at O, or he is a distance DELTA from O.
Let us assume for the moment that he is not at O but a distance DELTA from O. DELTA is either greater or less than 1/n.

If DELTA is greater than 1/n then the nth runner is “Lonely”.
If DELTA is less than 1/n we can repeat the process and examine the situation at time t = 2 x T. At time t = 2 x T, the first (n-1) runners are back again at O whereas the nth runner will be a distance 2 x DELTA from O. This result is obtained from the simple application of the principles of Modular Arithmetic. If necessary this process can be repeated M times until: t = M x T, and M x DELTA > 1/n and the nth runner becomes “Lonely”. However, we have made the assumption that at time T, the nth runner is not at O, when the first (n-1) runners have coincided there. The question is – What conditions are necessary for this to be so? It is now clear that if the nth runner’s speed is a unique prime number i.e. a prime number which is not a factor of the tracks length [s1 x s2 x s3 ... x s(n-1)] , then he will not coincide at O with the other runners at time T.

Statement 1.If any runner’s speed is a prime number which is not a factor of any other runners speed then that runner will become lonely. 2.By extension, if the speeds of all n runners are unique prime numbers then at some point all n runners become Lonely. 3.The Lonely Runner Conjecture is true for any n runners in the special case that each runner’s speed is a unique prime number.

The Case of Arbitrary Integers We now attempt to make the argument that the Lonely Runner Conjecture is true for any arbitrary set of n integer speeds. In order to do this we must introduce one additional concept as follows: We introduce the idea of a 0th runner who runs at a speed s0. He runs along with n other runners, who run at speeds (s0+s1), (s0+s2), (s0+s3),..., (s0+sn). For the purposes of this analysis, we have created an analogous case to the original case, in which the 0th runner has taken the place of the origin (starting point) in the original case. Because, relative to the 0th runner, the speeds of the other runners are s1, s2, s3,..., sn, as in the original case. That is to say, any case of n runners running at speeds s1, s2, s3, ..., sn (the original case), is equivalent to a case of (n+1) runners running at speeds s0, (s0+s1), (s0+s2), (s0+s3), ..., (s0+sn) where the 0th runner is equivalent to the origin in the original case. However, in both cases, it is allowable that we maintain our definition of “Lonely” as being a distance 1/ n.

Statement (4) If ANY runner becomes “Lonely” in a case when (n+1) runners are running at speeds s0, (s0+s1), (s0+s2), (s0+s3), ..., (s0+sn), for ANY integer s0, then THAT runner will also become “Lonely” in the original case when n runners run at speeds s1, s2, s3,... , sn.

A further explanation of Statement 4 is useful. At any time t, the relative position of, and distances between, all runners measured relative to the starting point in case 1 (the original case with n runners), is identical to the relative position of, and distances between, those runners when measured by the 0th runner in case 2 ( n+1, runners with speeds increased by s0).

We now consider the general case we wish to prove, i.e. that of n runners running at arbitrary integer speeds, s1, s2, s3,..., sn. We want to show that each individual runner can be shown to become “Lonely” at some point.

We refer first to Statement 4. If ANY runner becomes “Lonely” in a case when (n+1) runners are running at speeds s0, (s0+ s1), (s0+s2), (s0+s3), ..., (s0+sn), for ANY integer s0, then THAT runner will also become “Lonely” in the original case (when n runners run at speeds s1,s2,s3,...sn).

We understand from Statement 1 that all that is required for “Loneliness” to occur for a particular runner, in either case 1 or case 2, is that his speed is a unique prime number. However, it is important to note that this isn’t a necessary condition for “Loneliness” to occur.

We can now refine the argument is follows: Given a set of (n+1) runners, running at integer speeds s0, (s0+s1), (s0+s2), (s0+s3)... (s0+sn), is it possible to select an appropriate integer value for s0, for which the 1st runners speed is a unique prime number (not a factor of any other runners speed). If we can find such a value for s0, we have shown by reference to Statement 4, that he then must become “Lonely” in the original case. We then consider the 2nd runner and attempt to find another suitable value for s0. If we can do this for all runners, we have proven that all runners become “Lonely” in the original case and hence we have proven the conjecture.

Consider the 1st runner (not the 0th runner). His speed is (s0+s1). Can we find a value for s0 such that (s0+s1) is a prime number which is not a factor present in either (s0+s2), (s0+s3), (s0+s4)... or (s0+sn)?

This is easily done. 
Select a prime number larger than sn and call it P. We then set (s0+s1) = P, i.e. s0 = [P-s1]. The speeds of all the runners (from 0th to nth) is now: [P-s1], [P]*, [(P-s1) +s2], [(P-s1) + s3], ....., [(P-s1) + sn]

The 1st runner’s speed is P, it is a large prime number and it is clearly it is not a factor of any other runners speed. This is easily demonstrated since the largest term and all other terms are less than 2P, since P > sn. By showing that the value of the first runners speed, in this case, is prime and not a factor of any other runners speeds, we have shown that, in this case, he becomes “Lonely”. And according to Statement 4, by showing that he becomes “Lonely” in this case, we have shown that he becomes “Lonely” in the original case.

We can now consider the 2nd runner using the same value of P and the speeds are then: [P-s2], [(P-s2) + s1], [P]*, [(P-s2) + s3], ... [(P-s2) + sn].

Again by exactly the same reasoning it can be shown that P (the 2nd runners speed) is a prime number which is not a factor common to any other runners speed. Therefore he is “Lonely” in this case and the original case. By repeating this process it is possible to show that each runner becomes “Lonely” in the original case of n runners with arbitrary integer value speeds. Thus we have proven the Lonely Runner Conjecture. QED
Patrick Devlin