[math-fun] Marble problem
A clear marble has N tiny bubbles in it, numbered 1 through N. Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height). Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record? What if you measure distance from the contact point of the marble and floor?
What a great question! --Dan On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders. But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before. Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also. I do not yet see how to generalize this to the 3D case. On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
It's n(n-1)/2 not n(n-1)^2 lines, and each counts twice. Time to start proofreading. On Fri, Oct 17, 2014 at 5:34 PM, Tom Rokicki <rokicki@gmail.com> wrote:
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also.
I do not yet see how to generalize this to the 3D case.
On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Each point on the surface of the marble corresponds to some ordering, the ordering that prevails when that point is in contact with the floor. We can call two points equivalent if they induce the same ordering, and draw a map on the marble's surface whose regions, edges, and vertices represent the equivalence classes. (The edges and vertices correspond to degenerate orderings where two or more points are at equal heights.) I think the edges are all pieces of great circles; if the points are in general position there are k = n(n-1)/2 such circles. Now, k circles can cut a sphere into at most k^2 - k + 2 regions [A014206], so one might think that with three points you could get 8 orderings! Well, obviously something is wrong here: the problem is that because three points can be equidistant from the floor, the great circles sometimes meet in threes, not in pairs. For 4 points, the number of circles is 6; they meet in threes in 4 pairs of antipodal points, and there are also 3 pairwise meetings. I am running out of steam here because I don't have a scribbling surface handy. On Fri, Oct 17, 2014 at 8:36 PM, Tom Rokicki <rokicki@gmail.com> wrote:
It's n(n-1)/2 not n(n-1)^2 lines, and each counts twice. Time to start proofreading.
On Fri, Oct 17, 2014 at 5:34 PM, Tom Rokicki <rokicki@gmail.com> wrote:
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also.
I do not yet see how to generalize this to the 3D case.
On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, = 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-----Original Message----- From: math-fun [mailto:math-fun- bounces+davidwwilson=comcast.net@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Friday, October 17, 2014 9:39 PM To: math-fun Subject: Re: [math-fun] Marble problem
Each point on the surface of the marble corresponds to some ordering, the ordering that prevails when that point is in contact with the floor. We can call two points equivalent if they induce the same ordering, and draw a map on the marble's surface whose regions, edges, and vertices represent the equivalence classes. (The edges and vertices correspond to degenerate orderings where two or more points are at equal heights.)
I think the edges are all pieces of great circles; if the points are in general position there are k = n(n-1)/2 such circles. Now, k circles can cut a sphere into at most k^2 - k + 2 regions [A014206], so one might think that with three points you could get 8 orderings! Well, obviously something is wrong here: the problem is that because three points can be equidistant from the floor, the great circles sometimes meet in threes, not in pairs. For 4 points, the number of circles is 6; they meet in threes in 4 pairs of antipodal points, and there are also 3 pairwise meetings. I am running out of steam here because I don't have a scribbling surface handy.
Consider three points (bubbles). There are three great circles associated with pairs of these points. The planes of these great circles must pass through the center of the sphere (marble), they must also be perpendicular to the plane of the points. This implies that the planes of the great circle pass through the same axial line of the sphere, and cut the sphere surface into only 6 regions instead of the possible 8 by great circles in general position.
I think the generalization to the marble (3D) case is actually pretty easy, and I think the upper bound is n(n-1)(n-2) for n>2. That's what I'm putting my money on. -tom On Fri, Oct 17, 2014 at 5:34 PM, Tom Rokicki <rokicki@gmail.com> wrote:
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also.
I do not yet see how to generalize this to the 3D case.
On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
The solution for the 3D case is similar. Each pair of points defines a great circle across which the order of the points changes, so we need to count the number of disjoint regions on the surface of the sphere defined by all n(n-1)/2 great circles. That is, if we consider the graph whose vertices and edges are defined by the great circles, we need to count the faces. Again, it's easy to arrange for all the great circles to be distinct. The tricky part is that for every group of three points, all three of the great circles defined by pairs of those points intersect in just two vertices (each of degree six). However, we can arrange the points so that this is the only case in which more than two great circles intersect at a vertex. There are n(n-1)(n-2)/6 groups of three points, each of which defines two vertices of degree 6. There are n(n-1)(n-2)(n-3)/8 pairs of pairs of points, each of which defines two vertices of degree 4. So: V = n(n-1)(n-2)/3 + n(n-1)(n-2)(n-3)/4 = n(n-1)(n-2)(3n-5)/12 E = [6 * n(n-1)(n-2)/3 + 4 * n(n-1)(n-2)(n-3)/4] / 2 = n(n-1)(n-2)(n-1)/2 F = 2 + E - V = 2 + n(n-1)(n-2)(3n-1)/12 J.P. On Fri, Oct 17, 2014 at 9:28 PM, Tom Rokicki <rokicki@gmail.com> wrote:
I think the generalization to the marble (3D) case is actually pretty easy, and I think the upper bound is n(n-1)(n-2) for n>2. That's what I'm putting my money on.
-tom
On Fri, Oct 17, 2014 at 5:34 PM, Tom Rokicki <rokicki@gmail.com> wrote:
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also.
I do not yet see how to generalize this to the 3D case.
On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, = 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ahh, yes, that seems like a good solution. And it agrees with empirical search, placing the bubbles randomly. I wish I had come up with it. On Fri, Oct 17, 2014 at 7:05 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
The solution for the 3D case is similar. Each pair of points defines a great circle across which the order of the points changes, so we need to count the number of disjoint regions on the surface of the sphere defined by all n(n-1)/2 great circles. That is, if we consider the graph whose vertices and edges are defined by the great circles, we need to count the faces. Again, it's easy to arrange for all the great circles to be distinct.
The tricky part is that for every group of three points, all three of the great circles defined by pairs of those points intersect in just two vertices (each of degree six). However, we can arrange the points so that this is the only case in which more than two great circles intersect at a vertex.
There are n(n-1)(n-2)/6 groups of three points, each of which defines two vertices of degree 6. There are n(n-1)(n-2)(n-3)/8 pairs of pairs of points, each of which defines two vertices of degree 4. So:
V = n(n-1)(n-2)/3 + n(n-1)(n-2)(n-3)/4 = n(n-1)(n-2)(3n-5)/12
E = [6 * n(n-1)(n-2)/3 + 4 * n(n-1)(n-2)(n-3)/4] / 2 = n(n-1)(n-2)(n-1)/2
F = 2 + E - V = 2 + n(n-1)(n-2)(3n-1)/12
J.P.
On Fri, Oct 17, 2014 at 9:28 PM, Tom Rokicki <rokicki@gmail.com> wrote:
I think the generalization to the marble (3D) case is actually pretty easy, and I think the upper bound is n(n-1)(n-2) for n>2. That's what I'm putting my money on.
-tom
On Fri, Oct 17, 2014 at 5:34 PM, Tom Rokicki <rokicki@gmail.com> wrote:
For the circle case: There are at most n(n-1)^2 points at which the order changes (when the line connecting two dots is horizontal). It is easy to arrange points so these all have distinct angles (with small perturbations). So for the 2D case, it's clearly n(n-1) distinct orders. It's easy to show if all the angles are distinct, the n(n-1) distinct orders are also.
I do not yet see how to generalize this to the 3D case.
On Fri, Oct 17, 2014 at 5:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, = 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
> A clear marble has N tiny bubbles in it, numbered 1 through N. > > Roll the marble on the floor, then list the bubbles in order of their > distance from the floor (ignore situations where two or more bubbles are at the same height). > > Given an optimal distribution of bubbles, what is the largest possible > number of bubble orders you could record? > > What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ 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/ --
Very nice solution, J.P.! This reminds me a bit of an old problem I proposed a long time ago, whose generalization to one more like David's marble problem is as follows: QUESTION: Suppose given N bi-infinite cylinders of radius 1 in 3-space, whose axes all contain the origin. What is the maximum number of (curved) faces that their common intersection can have? --Dan On Oct 17, 2014, at 7:05 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
The solution for the 3D case is similar. Each pair of points defines a great circle across which the order of the points changes, so we need to count the number of disjoint regions on the surface of the sphere defined by all n(n-1)/2 great circles. . . . . . . F = 2 + E - V = 2 + n(n-1)(n-2)(3n-1)/12 J.P.
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
Thanks! And, interesting problem - I'll have to think about that. J.P. On Sat, Oct 18, 2014 at 1:12 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Very nice solution, J.P.!
This reminds me a bit of an old problem I proposed a long time ago, whose generalization to one more like David's marble problem is as follows:
QUESTION:
Suppose given N bi-infinite cylinders of radius 1 in 3-space, whose axes all contain the origin. What is the maximum number of (curved) faces that their common intersection can have?
--Dan
On Oct 17, 2014, at 7:05 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
The solution for the 3D case is similar. Each pair of points defines a great circle across which the order of the points changes, so we need to count the number of disjoint regions on the surface of the sphere defined by all n(n-1)/2 great circles. . . . . . . F = 2 + E - V = 2 + n(n-1)(n-2)(3n-1)/12 J.P.
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think a similar technique works, with one great circle per cylinder, only it's easier because (1) you can assume that no three great circles intersect in a point, and (2) you just need to count edges, so the answer should be 2N(N-1). Is that correct? J.P. On Sat, Oct 18, 2014 at 10:50 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Thanks! And, interesting problem - I'll have to think about that.
J.P.
On Sat, Oct 18, 2014 at 1:12 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Very nice solution, J.P.!
This reminds me a bit of an old problem I proposed a long time ago, whose generalization to one more like David's marble problem is as follows:
QUESTION:
Suppose given N bi-infinite cylinders of radius 1 in 3-space, whose axes all contain the origin. What is the maximum number of (curved) faces that their common intersection can have?
--Dan
On Oct 17, 2014, at 7:05 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
The solution for the 3D case is similar. Each pair of points defines a great circle across which the order of the points changes, so we need to count the number of disjoint regions on the surface of the sphere defined by all n(n-1)/2 great circles. . . . . . . F = 2 + E - V = 2 + n(n-1)(n-2)(3n-1)/12 J.P.
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you perform any similarity transformation on the set of bubbles (as long is the transformation keeps all the bubbles inside the marble), the set of achievable orders is the same. So, without loss of generality, we can *assume* that one of the bubbles, say, bubble 0, is in the center of the marble. I don't know how much this buys us. On Fri, Oct 17, 2014 at 8:04 PM, Neil Sloane <njasloane@gmail.com> wrote:
For the "circle" version, a person who might know the answer is William (Tom) Trotter, trotter@math.gatech.edu - suggest you ask him. It's just his kind of problem - and he is, or was, the editor of the journal "Order"!
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Oct 17, 2014 at 7:00 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I agree, great question. The 1-dimensiononal version is trivial, so the simplest (possibly-)nontrivial version is dimension 2 with a circle rolling on a 1-dimensional floor (I think we always want to assume codimension 1 here). So 1, 2, and 3 bubbles can be arranged in all ways by taking symmetrical positions, leaving 4 the first nontrivial case.The best I can do offhand is to put one in the center and three evenly spaced along the edge, which I think gives 12 orders.
But there are over 2000 entries in the OEIS starting 1, 2, 6, 12-24, >= 12, ... so this isn't even enough to see if the sequence has been studied before.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Oct 17, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What a great question!
--Dan
On Oct 17, 2014, at 2:54 PM, David Wilson <davidwwilson@comcast.net> wrote:
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just for the record, I authored this problem. Anyway, here is as far as I got: For the 2D case without reflection. N = 0 and 1 each have 1 possible order, they are what they are. Now consider two bubbles A and B in the disk. Draw line L through these bubbles, then draw diameter line D through the center of the disk perpendicular to L. Let X and Y be the endpoints of the diameter on the disk (antipodal points). As you roll the disk, the order of A and B changes precisely as X or Y touches the floor. Call X and Y the "exchange points" for A and B. The exchange points slice the disk boundary into two open semicircular arcs. When one of these arcs touches the floor, A and B are in order AB, when the other touches the floor, they are in order BA. Now consider N >= 2 bubbles in general position on the disk. There are choose(N, 2) = N(N-1)/2 distinct pairs of bubbles. We can perturb the bubble locations so that no two lines are parallel (I think this is implied by general location). Since no two lines are parallel, each line determines a unique pair of antipodal exchange points on the disk, giving are N(N-1) exchange points on the disk. These exchange points divide the disk into N(N-1) arcs, let's call these "order arcs". Now suppose the disk touches the floor at point A on the disk, and roll it so it touches point B on the disk. I leave it to you to show - If A and B are on the same order arc, the bubbles are in the same order. - If A and B are in different order arcs, the bubbles are in different order. I believe this shows that in the 2D case, - For N = 0 or 1, there is 1 bubble order - For N >= 2, there are at most N(N-1) bubble orders. The 3D problem is harder. In this case, for 2 bubbles A and B, you draw a line through the bubbles, then take the plane through the center of the marble perpendicular to this line. This plane intersects the marble surface in an "exchange great circle". If the marble touches the floor in one hemisphere of this great circle, the bubble order is AB, if in the other, BA. Again, for N >= 2 bubbles, there are N(N-1)/2 lines, hence N(N-1)/2 exchange great circles. However, these great circles cannot be placed in general position on the marble surface, and the maximal number of "order regions" on the marble surface dissected by the great circles is not apparent.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, October 17, 2014 5:55 PM To: math-fun Subject: [math-fun] Marble problem
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks, for the good problem. I have an intuition regarding the distinct planes between three points in the 3D case, and I'm not fully successful chasing it. In particular, my n(n-1)(n-2) conjecture is clearly wrong (too small). The basic idea itself is simple. For every such plane, with infinitesimal movements, you can generate six distinct orders. The difficulty here is figuring out when identical orders can be generated by distinct planes. In the 2D case, those pair up nicely by linear rotation of the disk. In the 3D case, it's not as nice. I guess this is the intersection of three of your great circles. I guess the next step is to figure out the pattern on the surface you want those great circles to form, and then prove it is maximal. On Fri, Oct 17, 2014 at 6:57 PM, David Wilson <davidwwilson@comcast.net> wrote:
Just for the record, I authored this problem.
Anyway, here is as far as I got:
For the 2D case without reflection. N = 0 and 1 each have 1 possible order, they are what they are.
Now consider two bubbles A and B in the disk. Draw line L through these bubbles, then draw diameter line D through the center of the disk perpendicular to L. Let X and Y be the endpoints of the diameter on the disk (antipodal points). As you roll the disk, the order of A and B changes precisely as X or Y touches the floor. Call X and Y the "exchange points" for A and B. The exchange points slice the disk boundary into two open semicircular arcs. When one of these arcs touches the floor, A and B are in order AB, when the other touches the floor, they are in order BA.
Now consider N >= 2 bubbles in general position on the disk. There are choose(N, 2) = N(N-1)/2 distinct pairs of bubbles. We can perturb the bubble locations so that no two lines are parallel (I think this is implied by general location). Since no two lines are parallel, each line determines a unique pair of antipodal exchange points on the disk, giving are N(N-1) exchange points on the disk. These exchange points divide the disk into N(N-1) arcs, let's call these "order arcs".
Now suppose the disk touches the floor at point A on the disk, and roll it so it touches point B on the disk. I leave it to you to show - If A and B are on the same order arc, the bubbles are in the same order. - If A and B are in different order arcs, the bubbles are in different order.
I believe this shows that in the 2D case, - For N = 0 or 1, there is 1 bubble order - For N >= 2, there are at most N(N-1) bubble orders.
The 3D problem is harder. In this case, for 2 bubbles A and B, you draw a line through the bubbles, then take the plane through the center of the marble perpendicular to this line. This plane intersects the marble surface in an "exchange great circle". If the marble touches the floor in one hemisphere of this great circle, the bubble order is AB, if in the other, BA.
Again, for N >= 2 bubbles, there are N(N-1)/2 lines, hence N(N-1)/2 exchange great circles. However, these great circles cannot be placed in general position on the marble surface, and the maximal number of "order regions" on the marble surface dissected by the great circles is not apparent.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, October 17, 2014 5:55 PM To: math-fun Subject: [math-fun] Marble problem
A clear marble has N tiny bubbles in it, numbered 1 through N.
Roll the marble on the floor, then list the bubbles in order of their distance from the floor (ignore situations where two or more bubbles are at the same height).
Given an optimal distribution of bubbles, what is the largest possible number of bubble orders you could record?
What if you measure distance from the contact point of the marble and floor?
_______________________________________________ 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/ --
participants (7)
-
Allan Wechsler -
Charles Greathouse -
Dan Asimov -
David Wilson -
J.P. Grossman -
Neil Sloane -
Tom Rokicki