monta@cmu-cs-g.ARPA (Peter Monta) (12/28/84)
> Unless I've made a terribly stupid mistake in my program, the answer is 17. > Why 17, you ask? It's obvious: 17 is the largest integer less than 18 :-). > > Ed Sheppard > Bell Communications Research Yes, I got 17 too. The first solution of length 17 (lexicographic order) is ( 0 7/13 11/13 4/15 12/17 5/12 12/13 2/15 8/13 1/3 10/13 1/5 8/17 16/17 1/15 11/17 6/17 ) As to why there aren't solutions of length 18, the only feeling I have is that there are relatively few new terms in the 18th Farey list (six, compared with sixteen new terms at the 17th); this sort of constricts the search. I haven't even been able to show that there isn't a sequence whose first n terms is a solution for every n (except, of course, by computer program). Peter Monta ARPA: monta@cmu-cs-g UUCP: ...!rochester!cmu-cs-pt!cmu-cs-g!monta
lambert@boring.UUCP (12/30/84)
Like Ed Sheppard (25@epsilon.UUCP) and Peter Monta (208@cmu-cs-g.ARPA),
I found, by exhaustive search, solutions up to 17 points and none above.
Since these programs were developed independently, this is strong evidence
that the maximum number of points is indeed 17.
However, my program gave a different result for the lexicographically
first solution, namely:
p1:[0,1/17) p2:[4/7,7/12) p3:[6/7,13/15) p4:[2/7,5/17)
p5:[8/11,11/15) p6:[5/11,6/13) p7:[1/7,2/13) p8:[13/14,14/15)
p9:[3/8,5/13) p10:[9/14,11/17) p11:[3/14,3/13) p12:[11/14,4/5)
p13:[1/2,9/17) p14:[1/14,2/17) p15:[16/17,1) p16:[5/16,6/17)
p17:[11/17,12/17)
(``pi:[lo,hi)'' means, of course, ``lo <= p[i] < hi''.) The solution
reported by Peter Monta came sixth.
Why the maximum is 17, I do not know either. I take it that ``Why'' means
here: ``Give a short proof''. The program could easily be made to output a
proof, but that would be rather long. But maybe all proofs of the theorem
``max length = 17'' are long.
Some more data that may help to find a shorter proof: There are 1536
(= 2^9*3) solutions, half of which are the mirror images of the other half.
It is possible to identify a solution by the permutation formed by p1-p17.
For example, for the first solution (given above) that permutation is
1af5d83g7b4e92h6c, where a-h stand for 10-17. Now in all 1536 solutions,
p13 gets the code 9, so it is the median point. Furthermore, p5-p6 are
always either 5a or its mirror image, d8. Also, p9 is either 7 or b, p11
is either 4 or e, and p16 is either 6 or c.
--
Lambert Meertens
...!{seismo,philabs,decvax}!mcvax!lambert@boring.UUCP
CWI (Centre for Mathematics and Computer Science), Amsterdammonta@cmu-cs-g.ARPA (Peter Monta) (12/31/84)
I received the following mail from alice!amo@Berkeley. I haven't yet been down to the library to look this up. We apparently have the correct answer, though :-). Date: Sun, 30 Dec 84 18:33:24 pst From: alice!amo@Berkeley To: monta@cmu-cs-g Subject: list of points problem The first published solution to that problem was by Berlekammp and Graham in J. Number Theory 2 (1970), 152-161. (The answer si 17.) Another solution was published some years later by Warmus, but I don't have the exact reference. Feel free to post this to net.math.
lambert@boring.UUCP (12/31/84)
Excerpt from letter received in reply to my article 6268@boring: > The first published solution to that problem was by Berlekamp and > Graham in J. Number Theory 2 (1970), 152-161. (The answer is 17.) > Another solution was published some years later by Warmus. I have not looked this up, our library being closed. If the article contains interesting insights, I will post a summary. -- Lambert Meertens ...!{seismo,philabs,decvax}!mcvax!lambert@boring.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam