Andy Latto <andy.latto@pobox.com> wrote:
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.
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.
Since nobody has responded.... For any three of the points, the perpendicular bisectors will always meet at a point. Hence for 3 points the plane will be divided into 6 regions, not 7. For N points, the plane will be divided into N-choose-3 fewer orderings than you suggest. Disclaimer: I can't take full credit for this discovery. Some guy named Euclid beat me to it.