wu :: forums
« wu :: forums - "Integer" Packing »

Welcome, Guest. Please Login or Register.
May 14th, 2021, 3:27am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: towr, Eigenray, Grimbal, SMQ, Icarus, william wu, ThudnBlunder)
   "Integer" Packing
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: "Integer" Packing  (Read 4311 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
"Integer" Packing  
« on: Sep 14th, 2006, 4:03am »
Quote Quote Modify Modify

Consider packing spheres into 3-dimensional space, such that the centers of spheres can be put only at the points with integral coordinates.
 
What maximum density can be obtained by such a packing?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #1 on: Sep 14th, 2006, 4:26am »
Quote Quote Modify Modify

Depends on the size of the spheres, doesn't it?
If you rescale the grid and spheres, such that you end upo with unit spheres, then the larger the spheres you start with, the better the coordinates can approximate the real-number coordinates for densest packing.  
 
And of course if the spheres have a radius of half a unit or less, the best you can do is a cube packing.
« Last Edit: Sep 14th, 2006, 4:28am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Whiskey Tango Foxtrot
Uberpuzzler
*****



Sorry Goose, it's time to buzz a tower.

   
Email

Gender: male
Posts: 1667
Re: "Integer" Packing  
« Reply #2 on: Sep 14th, 2006, 4:53am »
Quote Quote Modify Modify

Maybe he meant for us to generalize it Icarus.
IP Logged

"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: "Integer" Packing  
« Reply #3 on: Sep 14th, 2006, 5:17am »
Quote Quote Modify Modify

on Sep 14th, 2006, 4:26am, towr wrote:
Depends on the size of the spheres, doesn't it?
If you rescale the grid and spheres, such that you end upo with unit spheres, then the larger the spheres you start with, the better the coordinates can approximate the real-number coordinates for densest packing.

 Huh Could you please elaborate on this? I am not sure I understand this.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #4 on: Sep 14th, 2006, 6:42am »
Quote Quote Modify Modify

on Sep 14th, 2006, 5:17am, Barukh wrote:
Huh Could you please elaborate on this? I am not sure I understand this.
By rescaling, effective you use rational coordinates.
And for every set of real coordinates, you can find rational coordinates approximating them up to an arbitrarily small error.
Hence the maximum density you can achieve is arbitrarily close to that for real coordinates.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
irrational
Junior Member
**





   


Gender: male
Posts: 52
Some clarity  
« Reply #5 on: Sep 14th, 2006, 9:27am »
Quote Quote Modify Modify

Barukh do you mean a cube when you say "3-D Space"  
 
or else, the space can be a sphere and 1 sphere for the whole space ... Density of space = Density of sphere Smiley
 
Can the spheres intersect ?
 
@towr I think the question calls for integral co-ordinates.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Some clarity  
« Reply #6 on: Sep 14th, 2006, 9:37am »
Quote Quote Modify Modify

on Sep 14th, 2006, 6:42am, towr wrote:
And for every set of real coordinates, you can find rational coordinates approximating them up to an arbitrarily small error.

Ah, got it. No, the approximate solutions are not allowed (or, if you wish, there is a restriction on the size of the spheres that prevents getting a solution with required accuracy – see also irrational’s remark  Wink).
 
on Sep 14th, 2006, 9:27am, irrational wrote:
Barukh do you mean a cube when you say "3-D Space"

A cube.
 
Quote:
Can the spheres intersect ?

No (it’s packing).
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: Some clarity  
« Reply #7 on: Sep 14th, 2006, 9:57am »
Quote Quote Modify Modify

on Sep 14th, 2006, 9:27am, irrational wrote:
@towr I think the question calls for integral co-ordinates.
That doesn't matter though; it's just a matter of multiplying by the divisor of whatever rationals you use in the rescaled version.
But Barukh just undercut that approach; if there's an upper limit to the ball size, it doens't work.
 
Oh well, my solution for balls with diameters of less than a unit still stands.. (putting one at all integral coordinates)
 
Quote:
Can the spheres intersect ?
If that were allowed, you could put an arbitrary number of spheres at each coordinate, or even at one. Grin
« Last Edit: Sep 14th, 2006, 10:00am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
irrational
Junior Member
**





   


Gender: male
Posts: 52
Re: "Integer" Packing  
« Reply #8 on: Sep 14th, 2006, 12:43pm »
Quote Quote Modify Modify

I think the best packing density of the spheres in a cube is ~ 74%.
 
Googled a bit and here you go!!  Wink  
 
Those grocers do know something about geometry Smiley Smiley
 
-------EDIT----------
Of course this is assuming that the 3 dimensions of the cube are also integers.
« Last Edit: Sep 14th, 2006, 12:44pm by irrational » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: "Integer" Packing  
« Reply #9 on: Sep 14th, 2006, 4:18pm »
Quote Quote Modify Modify

on Sep 14th, 2006, 12:43pm, irrational wrote:
I think the best packing density of the spheres in a cube is ~ 74%.

But with the face-centred and hexagonal packing that gives ~74%, some of the centres of the spheres must be at irrational coordinates, right?
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: "Integer" Packing  
« Reply #10 on: Sep 14th, 2006, 11:09pm »
Quote Quote Modify Modify

on Sep 14th, 2006, 4:18pm, THUDandBLUNDER wrote:

But with the face-centred and hexagonal packing that gives ~74%, some of the centres of the spheres must be at irrational coordinates, right?

What would you say, irrational?  Wink
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7515
Re: "Integer" Packing  
« Reply #11 on: Sep 15th, 2006, 4:33am »
Quote Quote Modify Modify

With a diameter of sqrt(2), you can put a sphere at every "even" coordinate (x+y+z is even) and get an optimal packing.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: "Integer" Packing  
« Reply #12 on: Sep 15th, 2006, 4:34am »
Quote Quote Modify Modify

Correct, Grimbal!  
 
But how do you show that your claim is correct?
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2840
Re: "Integer" Packing  
« Reply #13 on: Sep 15th, 2006, 1:08pm »
Quote Quote Modify Modify

on Sep 15th, 2006, 4:34am, Barukh wrote:
Correct, Grimbal!  
 
But how do you show that your claim is correct?

Quite easily:
 
hidden:

Any packing with spheres or diameter more than 1 can't have sphere-centres at more than half the lattice points as there'd then have to be at least one pair occupying adjacent lattice points which would then intersect. Since the proposed packing does have spheres centered on half the points, it is optimal for spheres with diameter bigger than 1 and not more than sqrt(2)
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: "Integer" Packing  
« Reply #14 on: Sep 15th, 2006, 11:27pm »
Quote Quote Modify Modify

on Sep 15th, 2006, 1:08pm, rmsgrey wrote:

Quite easily:

 
Nice!  Cheesy
IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: "Integer" Packing  
« Reply #15 on: Sep 16th, 2006, 7:00am »
Quote Quote Modify Modify

In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
 
--SMQ
IP Logged

--SMQ

rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2840
Re: "Integer" Packing  
« Reply #16 on: Sep 16th, 2006, 10:03am »
Quote Quote Modify Modify

on Sep 16th, 2006, 7:00am, SMQ wrote:
In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
 
--SMQ

Seems that way, but rather than proving the Kepler Conjecture, it's easier to prove optimality under the restricted conditions...
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: "Integer" Packing  
« Reply #17 on: Sep 17th, 2006, 12:27am »
Quote Quote Modify Modify

on Sep 16th, 2006, 7:00am, SMQ wrote:
In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
--SMQ

Yes, it is. The purpose of my question was to show that fcc can be placed in the Cartesian system in a way that the centers of the spheres are at integer coordinates.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #18 on: Sep 17th, 2006, 7:13am »
Quote Quote Modify Modify

So for which radii can we achieve this in an integer lattice?  
(Aside from [sqrt]2 and multiples thereof)
And are there interesting densest packings for values in between?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7515
Re: "Integer" Packing  
« Reply #19 on: Sep 18th, 2006, 10:05am »
Quote Quote Modify Modify

You can't have an optimal fcc in integer coordinates with diameters that are not a multiple of sqrt(2).
But I have no time yet to write the proof.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #20 on: Sep 18th, 2006, 1:52pm »
Quote Quote Modify Modify

on Sep 18th, 2006, 10:05am, Grimbal wrote:
You can't have an optimal fcc in integer coordinates with diameters that are not a multiple of sqrt(2).
Are you telling me that any cube that can be placed with its vertices on integer coordinates has integer sidelengths? Because that's what it comes down to.
 
(And in case someone wants to nitpick, I did mean integer multiples of [sqrt]2)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2840
Re: "Integer" Packing  
« Reply #21 on: Sep 19th, 2006, 6:05am »
Quote Quote Modify Modify

on Sep 18th, 2006, 1:52pm, towr wrote:

Are you telling me that any cube that can be placed with its vertices on integer coordinates has integer sidelengths? Because that's what it comes down to.
 
(And in case someone wants to nitpick, I did mean integer multiples of [sqrt]2)

I admit I'm not entirely gifted with 3D visualisation, but I can't seem to find any cubes with side length [sqrt]2 - Octahedra, yep; cubes with side-length 2, yep. No cubes of side-length [sqrt]2 though...
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #22 on: Sep 19th, 2006, 6:21am »
Quote Quote Modify Modify

on Sep 19th, 2006, 6:05am, rmsgrey wrote:
I admit I'm not entirely gifted with 3D visualisation, but I can't seem to find any cubes with side length [sqrt]2 - Octahedra, yep; cubes with side-length 2, yep. No cubes of side-length [sqrt]2 though...
That sidenote in my last post applied to my post before that; because any number is some real multiple of [sqrt]2...
So any cube with a sidelength that's not an integer would be fine.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
irrational
Junior Member
**





   


Gender: male
Posts: 52
Re: "Integer" Packing  
« Reply #23 on: Sep 19th, 2006, 10:05am »
Quote Quote Modify Modify

Dang it!!!... Grimbal beat me to it Smiley
 
But if you see this image of the maximum packing density then I think it will make it clear why the radius of the sphere should be sqrt(2) or multiples there of.
 

 
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13729
Re: "Integer" Packing  
« Reply #24 on: Sep 19th, 2006, 1:17pm »
Quote Quote Modify Modify

on Sep 19th, 2006, 10:05am, irrational wrote:
But if you see this image of the maximum packing density then I think it will make it clear why the radius of the sphere should be sqrt(2) or multiples there of.
Only if you can't fit noninteger cubes in the grid. Otherwise it's straightforward to show you can; just a matter of scaling (by noninteger factor) and rotating.
Hence the question, can that be done? There is no a priori reason I can think of why not, although I haven't been able to find another orthogonal set of 3 equal length vectors starting at the origin.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board