Victor Miller <victorsmiller@gmail.com> wrote:
Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
William R. Somsky wrote:
If done w/ sufficient resolution, and barring a measure-zero set of coincidences, your procedure w/ N dead presidents should result in N(N-1)/2 different orderings. And nice question -- I solved it while driving in the car to get dinner. :-)
I think you have an off-by-one error. ....
(You get one *change* in ordering per "line joining two of the points", not one *ordering*.)
Correct.
Very cute puzzle.
Thanks. Coming up with interesting puzzles is often even more difficult than solving them.
Believe it or not, this is related to the clever algorithm of Nimrod Megiddo for linear programming in 2 dimensions. The idea is that if you have N linear inequalities in 2 dimensions (which is what this problem had) the vertices of the polytope given by their intersection come from intersections of of pairs of the lines (there might be some degeneracy) which are N(N-1)/2.
Megiddo's idea for minimizing a linear form over the polytope was a divide and conquer, which done cleverly, only took time *linear* in N.
Interesting. I'm not a visual thinker, so I didn't solve the dead presidents puzzle visually. I did notice that it's the same solution as the number of orderings of distances to N random points on a line. I have no idea whether this is a coincidence, or whether in some sense these are the same puzzle. In other words, if you have N random points on a line, and you measure their distances from a point, there are always (except, again, in the case of measure-zero coincidences) exactly N(N-1)/2 + 1 possible different sort orders. Which sort order you get depends on where the point you measure the distance from is. That point doesn't have to be on the line. Also, if you have N random points in M-dimensional space, there are once again N(N-1)/2 + 1 possible different sort orders, *if* the points you measure the distances from are all constrained to a line. 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. Maybe I should write a simulation. For definiteness, I'll say the N points are distributed, with equal probability density per unit area, within a circle. The point the distances are measured from need not be within the circle. Would I get a different answer if, instead of a region of a plane, the distribution was over the whole of a sphere, a torus, or a Klein bottle? (Distances of course to be measured along the surface in each case.) What about instead of a Euclidian metric (sqrt(x^2+y^2)), using a Minkowski metric (sqrt(x^2-y^2))? But then how would I sort the imaginary distances?