So there being no discussion on my fallacious proof other than discussion of rot13, I figured it was time to post what's wrong with the proof and the correct solution. I had almost posted the below proof as the solution to the problem, but I stopped to check my algebra first by making sure the formula gave the right answer for small values of N. N=1 gives 1, and N=2 gives 2, which seems promising, but N=3 gives 7, which is a lot of different orderings for 3 things! I thought I had made an algebraic mistake for a while, but eventually realized my error was in logic, not algebra. The problem is that even if the set of N points is in general position, the set of N(N-1)/2 perpendicular bisectors is not! In particular, given any 3 of the points, A, B, and C, the three perpendicular bisectors these generate all meet in a point. To look at it another way, the perpendicular bisector of AB divides the plane into the "A before B" and "B before A" half-planes, but if you look at the 7 regions generated by 3 lines in the plane that don't intersect in a point, the bounded triangular region is the set of points that are closer to A than B, closer to B than C, and closer to C than A, and that doesn't exist. Except on a set of measure 0, these (N-2)(N-1)N/6 triple intersections are the only points where more than 2 lines intersect at a point, and no two lines are parallel as long as no 3 of the original points are colinear and we never have 4 points where AB is parallel to CD. So if we perturb the lines slightly, we'll have a configuration of N(N-1)/2 lines dividing the plane into (N^4 - 2 N^3 + 3 N^2 - 2N +8)/8 regions, as derived below. But (N^3 -3 N^2 +2N)/6 of these are small triangles that arise from perturbing the sets of three lines that intersect at a point. So we have to subtract these regions off, so we see that generically, given N points in the plane, If we order them by their distance from another point P, we can get (3 N^4 - 10 N^3 + 21 N^2 - 14 N + 24)/24 different orderings. Anyone want to try to extend this to higher dimensions? Is there any easy way to see, without doing the above algebra that when N is large there are approximately N^4/8 possible orderings? Andy Latto On Thu, Mar 31, 2016 at 7:17 AM, Andy Latto <andy.latto@pobox.com> wrote:
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
-- Andy.Latto@pobox.com