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
lizs@munnari.OZ (Liz Sonenberg) (12/20/84)
> >> 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? I still don't see the problem. After an *evenly distributed* list of k points has been chosen, exactly k of the subintervals [0, 1/(k+1) ), [1/(k+1), 2/(k+1)), ... , [ k/(k+1), 1) will contain one of the chosen points. By the pigeon-hole principle, there must be an interval [i/(k+1), (i+1)/(k+1)) that doesn't contain one of the points. Choosing the (k+1)th point in this interval will produce an *evenly distributed* list of k+1 points, won't it ? Since the first point can be chosen arbitrarily to get an *evenly distributed* list of 1 point, it seems to me that the list can be made arbitrarily large. David Wilson
lizs@munnari.OZ (Liz Sonenberg) (12/20/84)
> > I still don't see the problem. After an *evenly distributed* list of k points > has been chosen, exactly k of the subintervals > [0, 1/(k+1) ), [1/(k+1), 2/(k+1)), ... , [ k/(k+1), 1) will contain one of > the chosen points. By the pigeon-hole principle, there must be an interval > [i/(k+1), (i+1)/(k+1)) that doesn't contain one of the points. Choosing the > (k+1)th point in this interval will produce an *evenly distributed* list of > k+1 points, won't it ? OOPS. Sorry peoples, if I had seriously tried to answer my own question I ought to have seen my blunder immediately. David Wilson
holmes@dalcs.UUCP (Ray Holmes) (12/27/84)
> > >> 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? > > I still don't see the problem. After an *evenly distributed* list of k points > has been chosen, exactly k of the subintervals > [0, 1/(k+1) ), [1/(k+1), 2/(k+1)), ... , [ k/(k+1), 1) will contain one of > the chosen points. By the pigeon-hole principle, there must be an interval > [i/(k+1), (i+1)/(k+1)) that doesn't contain one of the points. Choosing the > (k+1)th point in this interval will produce an *evenly distributed* list of > k+1 points, won't it ? Since the first point can be chosen arbitrarily to > get an *evenly distributed* list of 1 point, it seems to me that the list > can be made arbitrarily large. > > David Wilson No - no - no At MOST k of the intervals will contain one of the points, probably several contain more than one (violating the condition) point. Ray