|
||||
|
Title: packing spheres inside a cube Post by JocK on Aug 27th, 2004, 12:44pm What is the smallest number N of unit diameter spheres that can be packed inside a cube with volume V < N ? |
||||
|
Title: Re: packing spheres inside a cube Post by Barukh on Aug 28th, 2004, 9:09am It's a nice problem, Jock! I believe there is at least one relevant thread on the site. Is [hide]143[/hide] the right answer for the 2-D case? :-/ |
||||
|
Title: Re: packing spheres inside a cube Post by JocK on Aug 28th, 2004, 12:14pm on 08/28/04 at 09:09:05, Barukh wrote:
The answer for the 2-D case is certainly smaller than that. If I am not mistaken, one can pack [hide]30[/hide] unit diameter circles inside a square of area [hide]29.75[/hide]. [hide](This follows from the fact that 6 rows of 5 touching spheres can be placed in a rectangle of size 5+x by 1+5[sqrt](1-x[sup2]), with 0 < x [le] 1/2. A square with approximate area 29.75 is obtained for x = (-4+5[sqrt]10)/26 [approx] 0.454284.)[/hide] |
||||
|
Title: Re: packing spheres inside a cube Post by Barukh on Aug 29th, 2004, 1:05am on 08/28/04 at 12:14:33, JocK wrote:
Of course! My mistake was that I considered the densest circle packing only... ??? |
||||
|
Title: Re: packing spheres inside a cube Post by Barukh on Sep 2nd, 2004, 5:31am OK, for the original 3-D problem: 1. I have a fairly simple demonstration that N=63 may be arranged that way. 2. I have some evidence that N=31 may be the smallest number (much effort of other people is involved). I will elaborate on this later. What would you say, Jock? :D |
||||
|
Title: Re: packing spheres inside a cube Post by JocK on Sep 2nd, 2004, 4:02pm on 09/02/04 at 05:31:29, Barukh wrote:
Nice... :) And yes, a cubic close packing of 32 unit diameter spheres fits inside a cube of volume (1+3/[sqrt]2)[sup3] [approx] 30.41. Leave out one of the 32 spheres and you have 31 spheres inside a volume smaller than 31. But is 31 really the smallest number? I am curious to see your proof! :D J8)CK |
||||
|
Title: Re: packing spheres inside a cube Post by Barukh on Sep 3rd, 2004, 3:57am on 09/02/04 at 16:02:57, JocK wrote:
Hmm… I’ve got the same results, but I doubt it’s the cubic close packing (http://mathworld.wolfram.com/CubicClosePacking.html) that solves the case. See the attached drawings. In this configuration, spheres are organized in 4 layers, and each layer has a square packing (in 2-D case only two adjacent layers are shown). Every sphere touches at most 8 other spheres, whereas in CCP it is surrounded by 12 spheres. This configuration was built from the points of sphere centers kindly sent to me by Dave Boll (He’s got a nice optimal packing (http://users.frii.com/davejen/packing.html) site, which inspired me to think N=31 is the smallest number). It took me a while to reveal from the points the pattern of the whole configuration. Quote:
I don’t have a proof in its strict sense. I doubt anybody has it today. Rather, there is an ongoing effort to improve the best known packings, using mainly computational methods. As far as I know, the optimality is proved only for N = 2-6, 8-10. The following paper (http://www.combinatorics.org/Volume_11/PDF/v11i1r33.pdf) contains probably the latest results in optimal sphere packing to date. Note that for N=31 it gives the same attached configuration (figure 5). The difficulty of improving the existing packings supports my opinion that N=31 is the smallest number. It was a great pleasure to work on this problem, Jock! :D P.S. After investigating the configuration closely, I realized that my claim about surrounding spheres is not correct: the spheres in the central layers do have 12 neighbors... So, maybe it is indeed a CCP?! :-/ |
||||
|
Title: Re: packing spheres inside a cube Post by JocK on Sep 3rd, 2004, 2:42pm Barukh, you are perfectly right! Indeed it seems all computer simulations so far indicate that for the 3-D problem N=31 is the minimum. I didn't know this myself, but based on your last post I decided to post the problem on the sci.math newsgroup. (In fact, whilst I had worked out the N=31 solution, I just couldn't believe it yielded indeed the minimum.) Hugo Pfoertner directed me to the following integer sequences: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084616 (2-D case) and: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084826 (3-D case). These contain the solutions (computer simulation results) to both the 2-D (N=30) and the 3-D (N=31) problem. For the 3-D case, I find it very remarkable that whilst N=14 comes so close to satisfying the constraint V<N (14 unit-diameter spheres fit inside a cube of volume 14.071), this constraint is not satisfied until one reaches N=31. Moreover, for N=31 the constraint is satisfied in what seems to be a truly inefficient way (removing one sphere from a configuration of 32 spheres packed inside a cube). However, it is difficult to argue against these computer results... (Although - as you indicated - they render it very unlikely, they don't exclude the possibility that a lower N-value can be found!) Thanks for working this out in so much detail Barukh, I have learned a lot from it myself. Btw: no reasons for doubt, the 3-D solution constitutes a cubic close packing! J8)CK |
||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |