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?
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
Hello, what language is this : 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! ???? Google translate cannot even recognize what it is, Ok, I see, you have something big in your mouth and this is english, but unable to pronounce it correctly ?? Have a nice day. Simon Plouffe 2016-03-31 13:17 GMT+02:00 Andy Latto <andy.latto@pobox.com>:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's rot13. The name should tell you everything. Most good mail readers let you ungarble it with a single keystroke. On Thu, Mar 31, 2016 at 7:35 AM, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, what language is this : 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! ????
Google translate cannot even recognize what it is,
Ok, I see, you have something big in your mouth and this is english, but unable to pronounce it correctly ??
Have a nice day.
Simon Plouffe
2016-03-31 13:17 GMT+02:00 Andy Latto <andy.latto@pobox.com>:
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
_______________________________________________ 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
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
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
Apologies for my lack of imagination, but I'm not understanding the problem. Except the part about ignoring cases where 2 or more distances are equal. 1) Are the points labeled? 2) Are you taking N labeled points, (selected in advance from whatever space and then asking what are their different orders from a variable additional point? 3) How are they selected? ((( The first 2 paragraphs seem to assume that in at least 1D, however they be selected there is going to be one answer, just a function of N. Possible, but not immediately clear to me. But then in paragraphs 3 and 4, you are considering some probability distribution and mentioning a simulation, indicating that you agree that (in general) the answer is not necessarily just a function of N. ))) Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly? Many thanks, Dan
On Mar 30, 2016, at 8:35 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
[I]f 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?
A related question: Suppose I have two sets of n points in R^m, A and B. How hard is it to find the bijection A -> B that minimizes the sum of squared distances? For m=1 there’s a very efficient algorithm (your puzzle for the day), but for m>1 the best I know is solving the general minimum-weight bi-partite matching problem that grows as n^3 (for fixed m). The case where m grows with n might be interesting because a random set of points will often look quasi 1-dimensional when there are many axes to choose from. -Veit
On Mar 31, 2016, at 11:38 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Apologies for my lack of imagination, but I'm not understanding the problem. Except the part about ignoring cases where 2 or more distances are equal.
1) Are the points labeled?
2) Are you taking N labeled points, (selected in advance from whatever space and then asking what are their different orders from a variable additional point?
3) How are they selected?
((( The first 2 paragraphs seem to assume that in at least 1D, however they be selected there is going to be one answer, just a function of N. Possible, but not immediately clear to me.
But then in paragraphs 3 and 4, you are considering some probability distribution and mentioning a simulation, indicating that you agree that (in general) the answer is not necessarily just a function of N. )))
Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly?
Many thanks,
Dan
This is a discrete version (if n is finite) of Optimal Transport. Too hairy for my feeble mind, but folks around here think it's important for fluid simulation among other things. https://en.wikipedia.org/wiki/Transportation_theory_(mathematics) On Fri, 1 Apr 2016, Veit Elser wrote:
A related question:
Suppose I have two sets of n points in R^m, A and B. How hard is it to find the bijection A -> B that minimizes the sum of squared distances?
For m=1 there’s a very efficient algorithm (your puzzle for the day), but for m>1 the best I know is solving the general minimum-weight bi-partite matching problem that grows as n^3 (for fixed m). The case where m grows with n might be interesting because a random set of points will often look quasi 1-dimensional when there are many axes to choose from.
-- Tom Duff. I'm down with the relative thingy.
On Thu, Mar 31, 2016 at 11:38 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Apologies for my lack of imagination, but I'm not understanding the problem. Except the part about ignoring cases where 2 or more distances are equal.
1) Are the points labeled?
I don't know how to make sense of "counting the number of orderings" if the points are unlabeled; The order is "A point, then another point, then another point..."
2) Are you taking N labeled points, (selected in advance from whatever space and then asking what are their different orders from a variable additional point?
Yes, I think that's correct/
3) How are they selected?
((( The first 2 paragraphs seem to assume that in at least 1D, however they be selected there is going to be one answer, just a function of N. Possible, but not immediately clear to me.
But then in paragraphs 3 and 4, you are considering some probability distribution and mentioning a simulation, indicating that you agree that (in general) the answer is not necessarily just a function of N. )))
He was speculating that the answer was not constant, but I believe that I've proved that there's a maximum number of orderings, which occurs except on a measure-0 subset of possible N-tuples of points. For example, if 3 of the points are colinear, or if there are 4 points A, B, C, and D such that AB is parallel to CD, there will be fewer possible orderings.
The number of possible orderings depends on both N and the dimension of the space, but is otherwise generically constant. A previously posted an incorrect derivation of an incorrect formula as a find-the-error puzzle, but I'll follow up with what I think is a correct proof of the correct formula sometime this weekend. I think my derivation can be expanded to find the formula for larger numbers of dimensions, but it gets trickier, and I don't yet have a formula
Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly?
Keith, apologies if the problem you were thinking of is not the one I'm talking about above; if I've gotten it wrong, please post the problem you were thinking about, and we'll have two interesting problems to talk about! Andy
On Mar 30, 2016, at 8:35 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
[I]f 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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
On Apr 1, 2016, at 7:54 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Thu, Mar 31, 2016 at 11:38 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Apologies for my lack of imagination, but I'm not understanding the problem. Except the part about ignoring cases where 2 or more distances are equal.
1) Are the points labeled?
I don't know how to make sense of "counting the number of orderings" if the points are unlabeled; The order is "A point, then another point, then another point..."
OK, but suppose we then relabel the points. Then we must get a new ordering, whatever the system is for ordering them. There are then N! possibilities for the orderings of the N given points, all of them distinct, given a fixed additional point to which the N distances are measured. So, despite this e-mail, I still don't understand the problem. —Dan
2) Are you taking N labeled points, (selected in advance from whatever space and then asking what are their different orders from a variable additional point?
Yes, I think that's correct/
3) How are they selected?
((( The first 2 paragraphs seem to assume that in at least 1D, however they be selected there is going to be one answer, just a function of N. Possible, but not immediately clear to me.
But then in paragraphs 3 and 4, you are considering some probability distribution and mentioning a simulation, indicating that you agree that (in general) the answer is not necessarily just a function of N. )))
He was speculating that the answer was not constant, but I believe that I've proved that there's a maximum number of orderings, which occurs except on a measure-0 subset of possible N-tuples of points. For example, if 3 of the points are colinear, or if there are 4 points A, B, C, and D such that AB is parallel to CD, there will be fewer possible orderings.
The number of possible orderings depends on both N and the dimension of the space, but is otherwise generically constant. A previously posted an incorrect derivation of an incorrect formula as a find-the-error puzzle, but I'll follow up with what I think is a correct proof of the correct formula sometime this weekend. I think my derivation can be expanded to find the formula for larger numbers of dimensions, but it gets trickier, and I don't yet have a formula
Keith, can you please express the problem rigorously so that the answers to my 3 questions above are included either explicitly or implicitly?
Keith, apologies if the problem you were thinking of is not the one I'm talking about above; if I've gotten it wrong, please post the problem you were thinking about, and we'll have two interesting problems to talk about!
Andy
On Mar 30, 2016, at 8:35 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
[I]f 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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Andy Latto -
Dan Asimov -
Keith F. Lynch -
Simon Plouffe -
Tom Duff -
Tom Rokicki -
Veit Elser