Very cute puzzle. 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. Victor On Sun, Mar 27, 2016 at 8:33 PM, William R Somsky <wrsomsky@gmail.com> wrote:
Um.. Yeah.. Off by one. I gave how many changes of orderings there are, so add one for the total number of orderings. DOH! ;-) On Mar 27, 2016 04:01, "Gareth McCaughan" <gareth.mccaughan@pobox.com> wrote:
On 27/03/2016 03:38, 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.
N=1: N(N-1)/2 = 0, but obviously there's one ordering.
N=2: N(N-1)/2 = 1. Suppose we have A (born 0, died 1) and B (born -1, died 2). Then just "born" and "died" already give us both possible orderings.
N=3: N(N-1)/2 = 3. Suppose we have A(0..0), B (1..2) and C(0..3). Then, if h is very small and positive, we have the following orderings: - b + h(d-b): A < C < B - b - h(d-b): C < A < B - b + 1(d-b): A < B < C - b - 9(d-b): C < B < A
(You get one *change* in ordering per "line joining two of the points", not one *ordering*.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun