Problems & Puzzles:
Puzzles
Puzzle
64.
The Strange Ruler (TWA Baumann)
You are given a ruler without any graduation. Label the beginning
of the ruler with 'zero' and the end with 'm' (= maximum distance from
zero). Fix the grading lines for integral units of length from 0 to m.
Set two marks on different grading lines, so that each mark is in
another half of the ruler. Then set the 3rd mark on a free grading
line, so that now each mark is in another third of the ruler. Go on
this way until setting the nth mark (the last possible one). Of
course: All marks (and m) must be prime numbers.
The puzzle is to find a solution with maximum n. If there are
several solutions find this one with minimum m. Regard: The
mark (label) 'm' is only a limit. 'm' is not part of the last xth.
Example: If you choose m=13 you could set the first two
marks on grading lines 2 and 11. Now '2' is in the first half of the
ruler (0 < 2 < 13/2) and '11' is in the second half (13/2 <
11 < 13). The third mark could be placed on '7'. Then the 3 marks
are in different thirds: 0 < 2 < 13/3, 13/3 < 7 < 26/3,
26/3 < 11 < 13. Now you could set the fourth mark on '5' ... But
of course m=13 is too small to get the maximum n.
Remark: The puzzle is already known with integers, and it is
proved that in this case the maximum n is ... (you will find it out).
But now… we have to deal with primes.
At last, one solution was received for this old & noble
puzzle. Giovanni Resta wrote (Abril, 08):
Puzzle 64 is based on a famous problem.
Some details are here:
http://mathworld.wolfram.com/18PointProblem.html
The quite counterintuitive result is that in general
the maximum number of points that it is possible
to add is 17.
I performed an exhaustive search and the results are:
1) For integers the minimal M is 52 and one of the
possible soluzion is given by the 17 numbers:
{22,37,3,48,14,28,44,9,32,18,40,6,25,51,12,35,21}
2) The minimal prime M is 367 and the 17 prime points are
{2,211,317,107,269,167,53,347,139,239,79,293,191,29,
331,127,223}
Find below a description of the method I used.
First of all I used the solution by Warmus cited in
http://mathworld.wolfram.com/18PointProblem.html
this solution is given as a set of inequalities like
4/7 <= x1 < 7/12
2/7 <= x2 < 5/17
and so on, which give an infinite family of real solutions for a ruler
of unitary length.
As a first approach, just to obtain a nonminimal solution to
be used as an upperbound, I multiplied
the 17 given inequalities for various prime values of M
(the length of the ruler) to obtain a set of inequalities for which
all the x1, x2, ..., x17 can assume prime values.
I was sure I could find a solution in this way: it was only a matter
of how much I had to enlarge the ruler so that each of the above
inequality encompass a prime number.
In this way I found the smallest solution to be the one
with M=509.
To determine if this was the smallest solution (it is not!)
I wrote a very little recursive program that works as follows:
First of all I fix a prime value of M<=509 to be the ruler length.
Then I consider all the pairs x1,x2 of primes less than M.
Note that the first two numbers can be exchanged (this is not
true in general for subsequent numbers) so I can assume x1 < x2.
Now I check if x1,x2 are "legal", i.e., for k=2,3,...,17
they fall in different kth of the segment.
If so, I invoke the recursive procedure.
The recursive procedure receive a set of 2 <= h <= 16 "legal"
points and try to add the next one.
To do so, it adds a point not already taken and check if the
new set of h+1 point is "legal", i.e., for k=h+1,h+2,...,17
the points fall in distinct kth of the segment.
If this is possible the procedure calls itself with h+1 points,
otherwise return.
Using this method I found in few minutes that the smallest
solution in integers has M=52 and in about one hour that
the smallest solution in primes has M=367.
***
