On Wed, Mar 30, 2016 at 11:35 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
But now I'm wondering about the more general case. For instance the number of sort orders of distances to N random points in a plane, as measured from any point in the plane. I think it would not be a constant.
Here's a fallacious proof I came up with for the wrong answer. I had fun figuring out the fallacy, so maybe some other funsters will too. There's a hint as to what's wrong in rot13 at the bottom; I'll post the fallacy, together with the correct answer, in a day or two. For any two of the points, A, B, draw the perpendicular bisector of AB. If we measure from a point on one side of this bisector, A will come before B in the ordering, while if we measure from a point on the other side, B will come before A. So with N points, we have N(N-1)/2 bisectors dividing up the plane into regions, and we'll get a different ordering for each region. If we have K lines in the plane in general position, they divide the plane into K(K + 1)/2 + 1 regions; this is easily seen by induction; when we add the K'th line, it intersects the existing K-1 lines in K points, dividing it into K pieces (K-2 segments and 2 rays); each piece divides one planar region in 2, so we have added K regions, so K lines give us the 1 region we start with plus 1 + 2 + 3 + .... + K more. So with N points, we have N(N-1)/2 perpendicular bisectors, so they divide the plane into 1 + (N(N-1)/2)((N(N-1)/2) + 1) / 2 = (N^4 - 2 N^3 + 3 N^2 - 2N + 8)/8 possible orderings. V jnf unccl jvgu guvf fbyhgvba, hagvy V abgvprq gung jura A vf guerr, guvf tvirf frira qvssrerag beqrevatf, naq gurer ner bayl fvk gbgny beqrevatf bs guerr guvatf! Andy