[math-fun] Question someone posted to sci.math.research
Here's a possibly interesting question that someone signing his name as Brendan posted to sci.math.research. I have edited it slightly for clarity. << Consider a set of n points in the plane with diameter = 1, whose average (centroid) is the origin. Choose two of the points whose separation is greatest and replace each of them by their midpoint (so two separated points are replaced by two equal points). The number of points remains at n and their centroid remains at the origin. Again choose two points whose separation is (now) greatest... and so on repeatedly. Assume that for any given such point set, when there are choices to be made, they are made so as to *maximize* the number of steps lrequired to reach diameter = 1/2. Let f(n) be the maximum over all such point sets of this maximum number of steps until the point set reaches diameter = 1/2. What is f(n)?
--Dan
"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
On Monday 06 November 2006 22:12, Victor S. Miller wrote:
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).
Let's suppose we begin with the vertices of a regular 6n-gon inscribed in the half-unit circle. Divide them into 6 contiguous blocks of size n. Suppose that at each stage we take two points and just throw them away (which of course reduces the diameter at least as effectively as replacing them with the midpoint). After we've removed 3n points (no matter how), at least three of the blocks are still represented, therefore at least two noncontiguous blocks are still represented, therefore two points remain at distance at least 1/2. So it takes at least 3n/2 steps to get the diameter down below 1/2. -- g
participants (3)
-
Daniel Asimov -
Gareth McCaughan -
victor＠idaccr.org