Re: [math-fun] possible?
Bill Thurston> It's known (and not hard to prove, using C^\infty bump functions --- I
think this may have been originally due to Hassler Whitney) that every closed set in $R^n$ is the zero set of a C^\infty function. So, you can have two C^\infty surfaces intesecting in R^3 even intersect in much wilder sets than a simple arc --- e.g. they can intersect in a set that is connected but not locally connected, or whatever. If you're concerned about how the two surfaces cross, the construction allows you to independently choose the sign of the function in any component of the complement. On Dec 8, 2010, at 3:05 PM, Bill Gosper wrote:
Good grief, tutor Julian has plotted two infinitely differentiable surfaces intersecting in a simple arc that is not differentiable. --rwg __________ Thanks! This was probably a special case: The intersection became momentarily tangential, whereat the arc took an abrupt turn. It's a little hard to believe, even as you tumble the Mathematica plot, whose code I'll send soon. --rwg
It's a bit messy--here's a pic: http://gosper.org/pumpee.png --rwg On Wed, Dec 8, 2010 at 1:58 PM, Bill Gosper <billgosper@gmail.com> wrote:
Bill Thurston> It's known (and not hard to prove, using C^\infty bump functions --- I
think this may have been originally due to Hassler Whitney) that every closed set in $R^n$ is the zero set of a C^\infty function. So, you can have two C^\infty surfaces intesecting in R^3 even intersect in much wilder sets than a simple arc --- e.g. they can intersect in a set that is connected but not locally connected, or whatever. If you're concerned about how the two surfaces cross, the construction allows you to independently choose the sign of the function in any component of the complement. On Dec 8, 2010, at 3:05 PM, Bill Gosper wrote:
Good grief, tutor Julian has plotted two infinitely differentiable surfaces intersecting in a simple arc that is not differentiable. --rwg __________ Thanks! This was probably a special case: The intersection became momentarily tangential, whereat the arc took an abrupt turn. It's a little hard to believe, even as you tumble the Mathematica plot, whose code I'll send soon. --rwg
What is the minimum number of points that cannot be covered by unit diameter coins? This is from Naoki Inaba ( http://www.janko.at/Raetsel/Naoki/ ) A fuller explanation: Coins (of a unit diameter) can be packed in a square or hexagonal lattice. Either packing has holes. http://mathworld.wolfram.com/CirclePacking.html If there were 3 points on the plane, the coins could be moved to cover the points. If there were 3 million points on the plane, about 10% of them would be in the holes. (Packing density is pi sqrt(3)/6) Problem -- What is the minimum number of points that cannot be covered by coins? --Ed Pegg Jr
On 12/9/10, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
What is the minimum number of points that cannot be covered by unit diameter coins? This is from Naoki Inaba ( http://www.janko.at/Raetsel/Naoki/ )
A dangerous individual, judging by this specimen ... I suspect a fiendish oriental plot to destroy Western economies by distracting mathematicians from shopping for useless Christmas presents. WFL
A fuller explanation:
Coins (of a unit diameter) can be packed in a square or hexagonal lattice. Either packing has holes.
http://mathworld.wolfram.com/CirclePacking.html
If there were 3 points on the plane, the coins could be moved to cover the points.
If there were 3 million points on the plane, about 10% of them would be in the holes.
(Packing density is pi sqrt(3)/6)
Problem -- What is the minimum number of points that cannot be covered by coins?
--Ed Pegg Jr
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it. On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 12/9/10, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
What is the minimum number of points that cannot be covered by unit diameter coins? This is from Naoki Inaba ( http://www.janko.at/Raetsel/Naoki/ )
A dangerous individual, judging by this specimen ...
I suspect a fiendish oriental plot to destroy Western economies by distracting mathematicians from shopping for useless Christmas presents. WFL
A fuller explanation:
Coins (of a unit diameter) can be packed in a square or hexagonal lattice. Either packing has holes.
http://mathworld.wolfram.com/CirclePacking.html
If there were 3 points on the plane, the coins could be moved to cover the points.
If there were 3 million points on the plane, about 10% of them would be in the holes.
(Packing density is pi sqrt(3)/6)
Problem -- What is the minimum number of points that cannot be covered by coins?
--Ed Pegg Jr
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone? I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from. Steve Gray On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
Here's an upper bound. First, two simple facts that I won't take time to prove. My covering disks have radius 1. (1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.) (2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.) So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin. Result: 85 points. Veit On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely new approach is needed to go significantly below this. Veit On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks. On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely new approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Unless I'm misunderstanding something, these points are covered by three unit circles centered at 2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3 -tom On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely newr approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
Oops; forget the +1; just use 2/sqrt(3) e^ (2k pi i / 3). On Mon, Dec 13, 2010 at 9:37 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Unless I'm misunderstanding something, these points are covered by three unit circles centered at
2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3
-tom
On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely newr approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote:
I could quickly prove that 3 points can always be covered. I could not immediately prove the same for 4, though I have no doubt that it's true. My intuition is that an uncoverable set can be constructed with on the order of 15 to 20 points, but I really have no idea how to go about it.
On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com> wrote:
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
I got the idea, regardless, and while I haven't actually crunched the numbers, it does look like you beat my configuration. Yay, glory! You see what I was trying to do, though. I suspect that something like this will go through. I want to find the most devilish radius, and that suggests a new problem. Imagine two players, say "Allan" and "Tom". Allan draws an arbitrary circle on the plane, and then Tom positions a hexagonal close-packing of unit disks on the same plane. Then Tom has to pay Allan X grams of gold, where X is the size in radians of the largest contiguous arc of Allan's circle left uncovered by the disk array. (If the circle is completely covered, Tom pays nothing.) Assuming optimal play, how many grams of gold can Allan win? Once we know the answer to this problem, we can space points around that circle at slightly less than X radians, and this arrangement will solve the original problem, though it might not be minimal. It doesn't feel to me like the number of points is going to be much more than 7. On Mon, Dec 13, 2010 at 12:41 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Oops; forget the +1; just use 2/sqrt(3) e^ (2k pi i / 3).
On Mon, Dec 13, 2010 at 9:37 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Unless I'm misunderstanding something, these points are covered by three unit circles centered at
2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3
-tom
On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely newr approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
Obvious extension: unit spheres and n points in R3. d>3 dimensions, anyone?
I too have no idea how to go about these. It seems like it would have been good for Erdos, and it deserves a place in the next edition of Discrete and Computational Geometry. Fine problem! I've lost track of where the R2 version came from.
Steve Gray
On 12/10/2010 12:21 PM, Allan Wechsler wrote: > I could quickly prove that 3 points can always be covered. I could not > immediately prove the same for 4, though I have no doubt that it's true. My > intuition is that an uncoverable set can be constructed with on the order of > 15 to 20 points, but I really have no idea how to go about it. > > On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com
wrote:
>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Four circles in a hexagonal close-packing completely cover a circle of radius 1, of course. So for this to work, the arbitrary circle needs to have (optimally) a radius somewhat off of 1. If you add the center point, forcing one of the unit circles deeply into the the circle you draw, that might help reduce the point count. On Mon, Dec 13, 2010 at 9:56 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I got the idea, regardless, and while I haven't actually crunched the numbers, it does look like you beat my configuration. Yay, glory!
You see what I was trying to do, though. I suspect that something like this will go through. I want to find the most devilish radius, and that suggests a new problem.
Imagine two players, say "Allan" and "Tom". Allan draws an arbitrary circle on the plane, and then Tom positions a hexagonal close-packing of unit disks on the same plane. Then Tom has to pay Allan X grams of gold, where X is the size in radians of the largest contiguous arc of Allan's circle left uncovered by the disk array. (If the circle is completely covered, Tom pays nothing.) Assuming optimal play, how many grams of gold can Allan win?
Once we know the answer to this problem, we can space points around that circle at slightly less than X radians, and this arrangement will solve the original problem, though it might not be minimal. It doesn't feel to me like the number of points is going to be much more than 7.
On Mon, Dec 13, 2010 at 12:41 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Oops; forget the +1; just use 2/sqrt(3) e^ (2k pi i / 3).
On Mon, Dec 13, 2010 at 9:37 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Unless I'm misunderstanding something, these points are covered by three unit circles centered at
2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3
-tom
On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely newr approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
Here's an upper bound.
First, two simple facts that I won't take time to prove. My covering disks have radius 1.
(1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a disk of radius r that is completely uncovered. (Consider the maximum size disk that can be squeezed into the hole formed by three mutually tangent covering disks.)
(2) A disk of radius r placed anywhere in the plane, where there is a triangular lattice of minimum distance sqrt(3) r, will always contain at least one lattice point. (The triangular Delone cells define the largest disks that "fit" inside the lattice.)
So all I need to do is generate a triangular lattice with minimum distance sqrt(3) r and select all the lattice points within 1+2r of the origin.
Result: 85 points.
Veit
On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote:
> Obvious extension: unit spheres and n points in R3. > d>3 dimensions, anyone? > > I too have no idea how to go about these. It seems like it would have > been good for Erdos, and it deserves a place in the next edition of > Discrete and Computational Geometry. Fine problem! > I've lost track of where the R2 version came from. > > Steve Gray > > > On 12/10/2010 12:21 PM, Allan Wechsler wrote: >> I could quickly prove that 3 points can always be covered. I could not >> immediately prove the same for 4, though I have no doubt that it's true. My >> intuition is that an uncoverable set can be constructed with on the order of >> 15 to 20 points, but I really have no idea how to go about it. >> >> On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon<fred.lunnon@gmail.com
wrote:
>> > > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
I've been trying to do something very much like this, but using one point and two circles: (1) a point at the origin, (2) a circle with radius 1/2, and (3) a circle with radius 1+epsilon. I believe there's no way to cover all of (1),(2),(3) with unit circles, so it just remains to figure out how densely you need to pack points along (2) and (3) to guarantee there's an uncovered one. --Michael On Mon, Dec 13, 2010 at 12:59 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Four circles in a hexagonal close-packing completely cover a circle of radius 1, of course. So for this to work, the arbitrary circle needs to have (optimally) a radius somewhat off of 1.
If you add the center point, forcing one of the unit circles deeply into the the circle you draw, that might help reduce the point count.
On Mon, Dec 13, 2010 at 9:56 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I got the idea, regardless, and while I haven't actually crunched the numbers, it does look like you beat my configuration. Yay, glory!
You see what I was trying to do, though. I suspect that something like this will go through. I want to find the most devilish radius, and that suggests a new problem.
Imagine two players, say "Allan" and "Tom". Allan draws an arbitrary circle on the plane, and then Tom positions a hexagonal close-packing of unit disks on the same plane. Then Tom has to pay Allan X grams of gold, where X is the size in radians of the largest contiguous arc of Allan's circle left uncovered by the disk array. (If the circle is completely covered, Tom pays nothing.) Assuming optimal play, how many grams of gold can Allan win?
Once we know the answer to this problem, we can space points around that circle at slightly less than X radians, and this arrangement will solve the original problem, though it might not be minimal. It doesn't feel to me like the number of points is going to be much more than 7.
On Mon, Dec 13, 2010 at 12:41 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Oops; forget the +1; just use 2/sqrt(3) e^ (2k pi i / 3).
On Mon, Dec 13, 2010 at 9:37 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Unless I'm misunderstanding something, these points are covered by three unit circles centered at
2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3
-tom
On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
I managed to reduce the number of points, such that one must go uncovered, to 55. It's a simple modification of my earlier construction. An entirely newr approach is needed to go significantly below this.
Veit
On Dec 11, 2010, at 8:29 AM, Veit Elser wrote:
> Here's an upper bound. > > First, two simple facts that I won't take time to prove. > My covering disks have radius 1. > > (1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a > disk of radius r that is completely uncovered. (Consider the maximum > size disk that can be squeezed into the hole formed by three mutually > tangent covering disks.) > > (2) A disk of radius r placed anywhere in the plane, where there is a > triangular lattice of minimum distance sqrt(3) r, will always contain at > least one lattice point. (The triangular Delone cells define the largest > disks that "fit" inside the lattice.) > > So all I need to do is generate a triangular lattice with minimum distance > sqrt(3) r and select all the lattice points within 1+2r of the origin. > > Result: 85 points. > > Veit > > On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote: > >> Obvious extension: unit spheres and n points in R3. >> d>3 dimensions, anyone? >> >> I too have no idea how to go about these. It seems like it would have >> been good for Erdos, and it deserves a place in the next edition of >> Discrete and Computational Geometry. Fine problem! >> I've lost track of where the R2 version came from. >> >> Steve Gray >> >> >> On 12/10/2010 12:21 PM, Allan Wechsler wrote: >>> I could quickly prove that 3 points can always be covered. I could not >>> immediately prove the same for 4, though I have no doubt that it's true. My >>> intuition is that an uncoverable set can be constructed with on the order of >>> 15 to 20 points, but I really have no idea how to go about it. >>> >>> On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon< fred.lunnon@gmail.com
wrote: >>> >> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
(This is my first post here, by the way. Rich Schroeppel invited me after my mention of the 00-1101 Post-Tag system on the Life mailing list.) It can be shown that a circle of radius 1+epsilon can only be covered by either an even number of *unit disks (the centres of which lie on two concentric circles) or an odd number of unit disks (where all centres are concyclic). Indeed, the radius of the circle and number of unit disks forces the arrangement of disks (up to rotation). *Assuming that all such unit disks are disjoint. Sincerely, Adam P. Goucher ----- Original Message ----- From: "Michael Kleber" <michael.kleber@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Monday, December 13, 2010 7:20 PM Subject: Re: [math-fun] Point covering problem
I've been trying to do something very much like this, but using one point and two circles: (1) a point at the origin, (2) a circle with radius 1/2, and (3) a circle with radius 1+epsilon. I believe there's no way to cover all of (1),(2),(3) with unit circles, so it just remains to figure out how densely you need to pack points along (2) and (3) to guarantee there's an uncovered one.
--Michael
On Mon, Dec 13, 2010 at 12:59 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Four circles in a hexagonal close-packing completely cover a circle of radius 1, of course. So for this to work, the arbitrary circle needs to have (optimally) a radius somewhat off of 1.
If you add the center point, forcing one of the unit circles deeply into the the circle you draw, that might help reduce the point count.
On Mon, Dec 13, 2010 at 9:56 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I got the idea, regardless, and while I haven't actually crunched the numbers, it does look like you beat my configuration. Yay, glory!
You see what I was trying to do, though. I suspect that something like this will go through. I want to find the most devilish radius, and that suggests a new problem.
Imagine two players, say "Allan" and "Tom". Allan draws an arbitrary circle on the plane, and then Tom positions a hexagonal close-packing of unit disks on the same plane. Then Tom has to pay Allan X grams of gold, where X is the size in radians of the largest contiguous arc of Allan's circle left uncovered by the disk array. (If the circle is completely covered, Tom pays nothing.) Assuming optimal play, how many grams of gold can Allan win?
Once we know the answer to this problem, we can space points around that circle at slightly less than X radians, and this arrangement will solve the original problem, though it might not be minimal. It doesn't feel to me like the number of points is going to be much more than 7.
On Mon, Dec 13, 2010 at 12:41 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Oops; forget the +1; just use 2/sqrt(3) e^ (2k pi i / 3).
On Mon, Dec 13, 2010 at 9:37 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Unless I'm misunderstanding something, these points are covered by three unit circles centered at
2/sqrt(3) e^ (2k pi i / 3 + 1) for 0 <= k < 3
-tom
On Mon, Dec 13, 2010 at 9:08 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm going to up the ante a little. I claim that I have a 7-point solution, but I haven't been able to prove it. The seven points are 1.01 e ^ (2k pi i / 7), for 0 <= k < 7. Gain glory by covering these seven points with a hexagonal close-packing of unit disks.
On Sun, Dec 12, 2010 at 1:14 PM, Veit Elser <ve10@cornell.edu> wrote:
> I managed to reduce the number of points, such that one must go > uncovered, to 55. It's a simple modification of my earlier construction. > An entirely newr approach is needed to go significantly below > this. > > Veit > > On Dec 11, 2010, at 8:29 AM, Veit Elser wrote: > > > Here's an upper bound. > > > > First, two simple facts that I won't take time to prove. > > My covering disks have radius 1. > > > > (1) A disk of radius 1+2r, with r = 2/sqrt(3) - 1, will always contain a > > disk of radius r that is completely uncovered. (Consider the maximum > > size disk that can be squeezed into the hole formed by three mutually > > tangent covering disks.) > > > > (2) A disk of radius r placed anywhere in the plane, where there is a > > triangular lattice of minimum distance sqrt(3) r, will always contain at > > least one lattice point. (The triangular Delone cells define the largest > > disks that "fit" inside the lattice.) > > > > So all I need to do is generate a triangular lattice with > > minimum > distance > > sqrt(3) r and select all the lattice points within 1+2r of the origin. > > > > Result: 85 points. > > > > Veit > > > > On Dec 10, 2010, at 5:55 PM, Stephen B. Gray wrote: > > > >> Obvious extension: unit spheres and n points in R3. > >> d>3 dimensions, anyone? > >> > >> I too have no idea how to go about these. It seems like it would have > >> been good for Erdos, and it deserves a place in the next > >> edition of > >> Discrete and Computational Geometry. Fine problem! > >> I've lost track of where the R2 version came from. > >> > >> Steve Gray > >> > >> > >> On 12/10/2010 12:21 PM, Allan Wechsler wrote: > >>> I could quickly prove that 3 points can always be covered. I could not > >>> immediately prove the same for 4, though I have no doubt that it's > true. My > >>> intuition is that an uncoverable set can be constructed with > >>> on the > order of > >>> 15 to 20 points, but I really have no idea how to go about it. > >>> > >>> On Fri, Dec 10, 2010 at 9:21 AM, Fred lunnon< fred.lunnon@gmail.com
> wrote: > >>> > >> > >> > >> > >> _______________________________________________ > >> math-fun mailing list > >> math-fun@mailman.xmission.com > >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (9)
-
Adam P. Goucher -
Allan Wechsler -
Bill Gosper -
Ed Pegg Jr -
Fred lunnon -
Michael Kleber -
Stephen B. Gray -
Tom Rokicki -
Veit Elser