Unsolved problems

The conjecture about the lonely runner

Problem:

Some athletes start together at the same starting point for a running contest over a circular track. They keep running clockwise around forever at fixed distinct speeds. At some instant of time each runner may be at equal distance d from the one who runs before him and the one behind him, so that the positions of the runners are evenly distributed over the track. But is there for each of them an instant of time when he is at distance at least d from any other runner?
The conjecture that JM Wills made in 1967 says there is such an instant of time. The problem is how to prove this. This problem has been solved for up to seven runners, but the general problem remains unsolved.

In mathematical terms, we may formulate the problem for k+1 runners as follows:
Given a positive integer k and k integers d1 , d2 , ... , dk without common prime divisor. Prove there is a positive real t such that for all i∈{1,2,..,k} the product tdi is at distance at least 1/(k+1) from the nearest integer.

First approach:

Denote the distance of any real number x from the nearest integer by ||x||.


The case k=1

In this case, since d1 has no prime divisors, d1 = 1. For t=1/2 we have ||td1|| = ||1/2|| ≥ 1/2.


The case k=2

We are looking for a positive real t such that ||td1|| ≥ 1/3 ∧ ||td2|| ≥ 1/3.

After perhaps rearranging d1, d2 we can proceed as follows:
Let d1 = r13i1 + r23i2 + ... + rn3in where 0 ≤ i1 < i2 < ... < in and r1, r2, ... , rn ∈ {1,2}.
Let d2 = s13j1 + s23j2 + ... + sm3jm where i1 ≤ j1 < j2 < ... < jm and s1, s2, ... , sm ∈ {1,2}.

Then d13-j1-1 = r13i1-j1-1 + r23i2-j1-1 + ... + rn3in-j1-1 = u3i1-j1-1 + v where u,v are nonnegative integers and 1 ≤ u ≤ 3j1-i1+1-1 and u is not divisible by 3.
And d23-j1-1 = s13-1 + s23j2-j1-1 + ... + sm3jm-j1-1, so d2 is already at distance 1/3 from the nearest integer.

We are now looking for a positive integer w such that t := w3-j1-1 satisfies our conditions.

If only w is not divisible by 3, this t will satisfy ||td2|| = 1/3.

In order to let t satisfy ||td1|| ≥ 1/3, too, we have to require furthermore that the product u*w modulo 3j1-i1+1 belong to the interval [3j1-i1, 2*3j1-i1].

But it is evident that such a w exists.


The case k=3

We are looking for a positive real t such that ||td1|| ≥ 1/4 ∧ ||td2|| ≥ 1/4 ∧ ||td3|| ≥ 1/4 .

After perhaps rearranging d1, d2, d3 we can proceed as follows:
Let d1 = r114i11 + r124i12 + ... + r1n14i1n1 where 0 ≤ i11 < i12 < ... < i1n1 and r11, r12, ... , r1n1 ∈ {1,2,3}.
Let d2 = r214i21 + r224i22 + ... + r2n24i2n2 where i11 ≤ i21 < i22 < ... < i2n2 and r21, r22, ... , r2n2 ∈ {1,2,3}.
Let d3 = r314i31 + r324i32 + ... + r3n34i3n3 where i21 ≤ i31 < i32 < ... < i3n3 and r31, r32, ... , r3n3 ∈ {1,2,3}.

Then d14-i31-1 = r114i11-i31-1 + r124i12-i31-1 + ... + r1n14i1n1-i31-1 = u14i11-i31-1 + v1 where u1, v1 are nonnegative integers and 1 ≤ u1 ≤ 4ik1-i11+1-1 and u1 is not divisible by 4.
And d24-i31-1 = r214i21-i31-1 + r224i22-i31-1 + ... + r2n24i2n2-i31-1 = u24i11-i31-1 + v2 where u2, v2 are nonnegative integers and 1 ≤ u2 ≤ 4i31-i11+1-1.
And d34-i31-1 = r314i31-i31-1 + r324i32-i31-1 + ... + r3n34i3n3-i31-1 = u34-1 + v3 where u3=r31 and v3 is a nonnegative integer.

We are now looking for a positive integer w such that t := w*4-i31-1 satisfies our conditions.

If only w is not divisible by 4, this t will satisfy ||td3|| ≥ 1/4.

In order to let t satisfy ||td1|| ≥ 1/4 and ||td2|| ≥ 1/4 too, we have to require furthermore that the products u1*w and u2*w modulo 4i31-i11+1 belong to the interval [(4i31-i11, 3*4i31-i11].

It seems evident that such a w exists.


The general case

We are looking for a positive real t such that ||td1|| ≥ 1/(k+1) ∧ ||td2|| ≥ 1/(k+1) ∧ .... ∧ ||tdk|| ≥ 1/(k+1) .

After perhaps rearranging d1, d2, ... , dk we can proceed as follows:
Let d1 = r11(k+1)i11 + r12(k+1)i12 + ... + r1n1(k+1)i1n1 where 0 ≤ i11 < i12 < ... < i1n1 and r11, r12, ... , r1n1 ∈ {1,2,..k}.
Let d2 = r21(k+1)i21 + r22(k+1)i22 + ... + r2n2(k+1)i2n2 where i11 ≤ i21 < i22 < ... < i2n2 and r21, r22, ... , r2n2 ∈ {1,2,..k}.
...
Let dk = rk1(k+1)ik1 + rk2(k+1)ik2 + ... + rknk(k+1)iknk where i(k-1)1 ≤ ik1 < ik2 < ... < iknk and rk1, rk2, ... , rknk ∈ {1,2,..k}.

Then d1(k+1)-ik1-1 = r11(k+1)i11-ik1-1 + r12(k+1)i12-ik1-1 + ... + r1n1(k+1)i1n1-ik1-1 = u1(k+1)i11-ik1-1 + v1 where u1, v1 are nonnegative integers and 1 ≤ u1 ≤ (k+1)ik1-i11+1-1 and u1 is not divisible by (k+1).
And d2(k+1)-ik1-1 = r21(k+1)i21-ik1-1 + r22(k+1)i22-ik1-1 + ... + r2n2(k+1)i2n2-ik1-1 = u2(k+1)i11-ik1-1 + v2 where u2, v2 are nonnegative integers and 1 ≤ u2 ≤ (k+1)ik1-i11+1-1.
...
And dk(k+1)-ik1-1 = rk1(k+1)ik1-ik1-1 + rk2(k+1)ik2-ik1-1 + ... + rknk(k+1)iknk-ik1-1 = uk(k+1)-1 + vk where uk=rk1 and vk is a nonnegative integer.

We are now looking for a positive integer w such that t := w*(k+1)-ik1-1 satisfies our conditions.

If only w is not divisible by k+1, this t will satisfy ||tdk|| ≥ 1/(k+1).

In order to let t satisfy ||tdi|| ≥ 1/(k+1) for i=1,2,..,k-1, too, we have to require furthermore that the product ui*w modulo (k+1)ik1-i11+1 belong to the interval [(k+1)ik1-i11, k*(k+1)ik1-i11].

We have to prove that such a w exists.


A computer program

We may use the following Pascal program to search for an approximation of the minimal t if k is at most 100 and the k given integers are within standard pascal range:

program unsolved;
var i,j,k:integer; t:real; d:array[1..100] of integer; noggoed:boolean;
function norm(x:real):real;
begin
  norm:=abs(x-round(x))
end;
begin
  writeln('k?'); readln(k);
  writeln('Geef ',k:3,' positieve integers');
  for j:=1 to k do begin writeln('d[',j:3,']?'); readln(d[j]) end;
  t:=0;
  repeat
    t:=t+0.00001;
    noggoed:=true; i:=0;
    while ((i < k) and noggoed) do
      begin i:=i+1; if norm(t*d[i]) < (1/(k+1)) then noggoed:=false end;
    if noggoed then
      begin
        writeln(t:13:5); for j:=1 to k do writeln(norm(t*d[j]):13:10);
        writeln; readln
      end
  until noggoed
end.


The 3n+1 conjecture

Problem:

Take an arbitrary positive integer n. If n is even, change it into n/2. If n is odd, change it into 3n+1. Show that if we repeat this procedure, we get 1 in the end.

First approach:

If n is even, then the probability that n/2 is even is 1/2 again. We count n ---> n/2 as one step.
If n is odd, then 3n+1 is even and the probability that (3n+1)/2 is even is 1/2 again. We count n ---> 3n+1 ---> (3n+1)/2 as one step.
If we neglect the +1 in (3n+1)/2 then after k steps we expect to have n*3(Σ(j=0 to k) j*(k over j))/2k/2k = n*3k/2/2k = n*(√3/2)k, which tends to 0 if k ---> ∞ unless we get 1 at some point.
So we should get 1 in the end.



HOME