monta@cmu-cs-g.ARPA (Peter Monta) (12/17/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)? > > Peter Monta > >> It seems to me that I must be missing something because >> this looks easy. If I understand it correctly we are asked to >> >> Greg Rawlins. ... solve a rather ill-stated problem. Here is a more precise formulation: Suppose we call a list of points ( p_1, p_2, ... , p_n ) in [0,1) *evenly distributed* if each segment of the form [i/n,(i+1)/n) for 0<=i<n contains a point in the list. The problem asks for a list of points ( p_1, p_2, ... , p_n ) such that ( p_1, p_2, ... , p_k ) is an evenly distributed list for *every* k between 1 and n, inclusive. What is the largest n for which one can find such a list? Notice that ( 0, 1/3, 2/3 ) is *not* a solution, since ( 0, 1/3 ) is already not an evenly distributed list. ( 0, 2/3, 1/3 ) *is*, however, a solution. Peter Monta ARPA: monta@cmu-cs-g UUCP: ...!rochester!cmu-cs-pt!cmu-cs-g!monta