wu :: forums « wu :: forums - "Integer" Packing » Welcome, Guest. Please Login or Register. May 14th, 2021, 3:27am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: towr, Eigenray, Grimbal, SMQ, Icarus, william wu, ThudnBlunder)    "Integer" Packing « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: "Integer" Packing  (Read 4311 times)
Barukh
Uberpuzzler

Gender:
Posts: 2276
 "Integer" Packing   « on: Sep 14th, 2006, 4:03am » Quote 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:
Posts: 13729
 Re: "Integer" Packing   « Reply #1 on: Sep 14th, 2006, 4:26am » Quote 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.

Gender:
Posts: 1667
 Re: "Integer" Packing   « Reply #2 on: Sep 14th, 2006, 4:53am » Quote 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:
Posts: 2276
 Re: "Integer" Packing   « Reply #3 on: Sep 14th, 2006, 5:17am » Quote 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.

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:
Posts: 13729
 Re: "Integer" Packing   « Reply #4 on: Sep 14th, 2006, 6:42am » Quote Modify

on Sep 14th, 2006, 5:17am, Barukh wrote:
 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:
Posts: 52
 Some clarity   « Reply #5 on: Sep 14th, 2006, 9:27am » Quote 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

Can the spheres intersect ?

@towr I think the question calls for integral co-ordinates.
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Some clarity   « Reply #6 on: Sep 14th, 2006, 9:37am » Quote 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  ).

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:
Posts: 13729
 Re: Some clarity   « Reply #7 on: Sep 14th, 2006, 9:57am » Quote 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.
 « Last Edit: Sep 14th, 2006, 10:00am by towr » IP Logged

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

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

I think the best packing density of the spheres in a cube is ~ 74%.

Googled a bit and here you go!!

Those grocers do know something about geometry

-------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:
Posts: 4489
 Re: "Integer" Packing   « Reply #9 on: Sep 14th, 2006, 4:18pm » Quote 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:
Posts: 2276
 Re: "Integer" Packing   « Reply #10 on: Sep 14th, 2006, 11:09pm » Quote 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?
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7515
 Re: "Integer" Packing   « Reply #11 on: Sep 15th, 2006, 4:33am » Quote 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:
Posts: 2276
 Re: "Integer" Packing   « Reply #12 on: Sep 15th, 2006, 4:34am » Quote Modify

Correct, Grimbal!

But how do you show that your claim is correct?
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2840
 Re: "Integer" Packing   « Reply #13 on: Sep 15th, 2006, 1:08pm » Quote 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:
Posts: 2276
 Re: "Integer" Packing   « Reply #14 on: Sep 15th, 2006, 11:27pm » Quote Modify

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

Nice!
 IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: "Integer" Packing   « Reply #15 on: Sep 16th, 2006, 7:00am » Quote 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

Gender:
Posts: 2840
 Re: "Integer" Packing   « Reply #16 on: Sep 16th, 2006, 10:03am » Quote 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:
Posts: 2276
 Re: "Integer" Packing   « Reply #17 on: Sep 17th, 2006, 12:27am » Quote 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:
Posts: 13729
 Re: "Integer" Packing   « Reply #18 on: Sep 17th, 2006, 7:13am » Quote 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:
Posts: 7515
 Re: "Integer" Packing   « Reply #19 on: Sep 18th, 2006, 10:05am » Quote 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:
Posts: 13729
 Re: "Integer" Packing   « Reply #20 on: Sep 18th, 2006, 1:52pm » Quote 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

Gender:
Posts: 2840
 Re: "Integer" Packing   « Reply #21 on: Sep 19th, 2006, 6:05am » Quote 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:
Posts: 13729
 Re: "Integer" Packing   « Reply #22 on: Sep 19th, 2006, 6:21am » Quote 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:
Posts: 52
 Re: "Integer" Packing   « Reply #23 on: Sep 19th, 2006, 10:05am » Quote Modify

Dang it!!!... Grimbal beat me to it

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:
Posts: 13729
 Re: "Integer" Packing   « Reply #24 on: Sep 19th, 2006, 1:17pm » Quote 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »