"Daniel" == Daniel Asimov <dasimov@earthlink.net> writes:
Daniel> Here's a possibly interesting question that someone signing Daniel> his name as Brendan posted to sci.math.research. I have Daniel> edited it slightly for clarity. Daniel> << Consider a set of n points in the plane with diameter = 1, Daniel> whose average (centroid) is the origin. Daniel> Choose two of the points whose separation is greatest and Daniel> replace each of them by their midpoint (so two separated Daniel> points are replaced by two equal points). .The number of Daniel> points remains at n and their centroid remains at the Daniel> origin. . Daniel> Again choose two points whose separation is (now) Daniel> greatest... and so on repeatedly. Daniel> Assume that for any given such point set, when there are Daniel> choices to be made, they are made so as to *maximize* the Daniel> number of steps lrequired to reach diameter = 1/2. Daniel> Let f(n) be the maximum over all such point sets of this Daniel> maximum number of steps until the point set reaches diameter = Daniel> 1/2. . Daniel> What is f(n)? >> Daniel> --Dan Here are some thoughts on it (by the way it was Brendan Mackay who posted it). If v_1, ..., v_n are the vectors corresponding to the n points, then define: L(v) := sum_{i < j} |v_i - v_j|^2 S(v) := sum_i |v_i|^2 where | | is the Euclidean norm. If v' denotes the sequence in which you replace v_1 and v_2 by (v_1 + v_2)/2 a little calculation yields: L(v) - L(v') = (n-1) |v_1 - v_2|^2 (this is not using the centroid assumption). So, if v_1, v_2 are chosen to have the maximal distance we have |v_1-v_2|^2 >= L(v)(n(n-1)/2). Thus L(v') <= (1-2/n) L(v). Using the centroid assumption we have L(v) = (n+1) S(v). Now use the fact that (1-2/n)^n is approximately e^-2. You find that in no more than n (log 4n)/2 steps that the radius (i.e the largest of the |v_i|) is at least halved. Note that this doesn't make any use of the fact that the points are in the plane. Mackay, in his post also mentions an "obvious lower bound" of c n for some c (but, it's not so obvious to me -- perhaps someone can enlighten me). Victor