monta@cmu-cs-g.ARPA (Peter Monta) (12/09/84)
A friend gave me this problem about a year ago, and I now know the answer, but not to my satisfaction. Consider a (bounded) line-segment. Choose point 1 anywhere on the segment. Then choose point 2 so that the first two points lie in different halves of the segment; choose point 3 so that the first three points all lie in different thirds of the segment; etc. What is the maximum number of points you can choose (before further choice becomes impossible)? It is convenient to consider a half-open segment, say [0,1[, and to regard 1/2 as belonging to the second half, 2/3 to the third third, etc. If you get an answer, and a compelling *reason* why the answer is true, I'd very much like to hear about it. Peter Monta ARPA: monta@cmu-cs-g UUCP: ...!rochester!cmu-cs-pt!cmu-cs-g!monta
pmontgom@sdcrdcf.UUCP (Peter Montgomery) (12/16/84)
> Consider a (bounded) line-segment. Choose point 1 anywhere on the segment. > Then choose point 2 so that the first two points lie in different halves of > the segment; choose point 3 so that the first three points all lie in > different thirds of the segment; etc. What is the maximum number of points > you can choose (before further choice becomes impossible)? > It is convenient to consider a half-open segment, say [0,1[, and to regard > 1/2 as belonging to the second half, 2/3 to the third third, etc. I believe you can go as far as you want. Use the fractional parts of multiples of the golden ratio (SQRT(5)-1)/2, or about 0.618. The sequence 0.618, 0.236, 0.854, 0.472, 0.090, 0.708, 0.326, ... seems to satisfy the requirements. I recall a picture in one of Donald Knuth's volumes of "The Art of Computer Programming" showing this sequence, but cannot locate that now. -- Peter Montgomery {aero,allegra,bmcg,burdvax,hplabs, ihnp4,psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom Don't blame me for the crowded freeways - I don't drive.
lambert@mcvax.UUCP (Lambert Meertens) (12/18/84)
>> Consider a (bounded) line-segment. Choose point 1 anywhere on the segment. [etc.] > I believe you can go as far as you want. Use the fractional parts of > multiples of the golden ratio (SQRT(5)-1)/2, or about 0.618. The sequence > 0.618, 0.236, 0.854, 0.472, 0.090, 0.708, 0.326, ... seems to satisfy the > requirements. Not so. Take n = 7, and consider p[i] = (i*phi) mod 1 --> floor(p[i]*n): p1 = 0.618 --> 4 p2 = 0.236 --> 1 p3 = 0.854 --> 5 p4 = 0.472 --> 3 p5 = 0.090 --> 0 p6 = 0.708 --> 4 p7 = 0.326 --> 2 So both p1 and p6 fall in segment 4, and the last segment, 6, is not represented. I have not (yet) tried to prove this, but it appears extremely unlikely to me that an infinite sequence could exist for which every initial segment is evenly distributed. Here is as far as I came using a backtracking method: 0 <= p1 < 1/10 1/2 <= p2 < 5/9 3/4 <= p3 < 7/9 1/4 <= p4 < 2/7 7/8 <= p5 < 8/9 3/8 <= p6 < 2/5 5/8 <= p7 < 2/3 1/8 <= p8 < 1/5 9/10 <= p9 < 1 2/5 <= p10 < 1/2 I do not claim that this is the only solution up to 10, nor that it cannot be extended. -- Lambert Meertens ...!{seismo,philabs,decvax}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam