Thursday, May 9, 2013

How to Estimate the Number of Candies in a Jar (and Pack Tightly)

Two related questions:
1. How do you pack balls (spheres) as tightly as possible?
2. How do you estimate the number of candies in a jar?

Packing Spheres Tightly

The relevant quantity to study is the following: given a certain amount of volume of space T, how much volume of balls S can we put into that space? The ratio S/T is called the packing factor, and it gives the proportion of space that is occupied by balls.

There are various ways to pack. The following picture shows three suggestions (the balls are sliced so that you only see the parts that are inside the cube):

In the left most figure (simple cubic), we see the "corners" of eight different balls; the packing is essentially putting balls on top of each other (and next to each other) in a grid like fashion.

In the right most (body centered cubic), we put one ball int he middle and surround it by eight other balls. So instead of stacking balls like a grid, they "sink in to each other".

The middle one (face centered cubic) is similar to body centered cubic in that the balls "sink in", but here we "smash them together" not only at their corners, but also on the sides (the blue balls).

It should be intuitively clear that the simple cubic is not the best way to pack balls as densely as possible.
In fact, the picture suggests that the face centered cubic is better than the body centered cubic.
More interesting, we would like to know the percentage of wasted space (or equivalently, used space) for each configuration, as well as the best we can in principle do.

Define some useful variables:
L = Length of one side in the cube.
R = Radius of a ball.

Packing Factor for Body Centered Cubic

Now we calculate the packing factor for the body centered cubic:

The factor 2 in S comes the fact that inside the volume T, we have 2 balls: the one in the middle, and the 8 other pieces, which are one eight in side each (it is quite easy to see that they can be put together into a ball by looking at the picture).

Dividing S by T should give the answer, except that we haven't figured out the relationship between the length of the cube, L, and the radius of the balls, R.

The diagonal from side corner to the opposite (farthest away) will be of length $D = \sqrt{3} L$, which can be seen as follow:  a diagonal across one surface of the cube is $\sqrt{2} L$ by the Pythagorean theorem, and so  $D^2 = L^2 + (\sqrt{2} L)^2 = 3 L^2$.

Looking at the picture (c) above, the balls on each corner touch the middle one, so looking at a straight line from one corner to the other (of length D), we are traversing 4R of length: $D = 4R$. From our two identities involving D, we get:

$L = \frac{4L}{\sqrt{3}}$

We can now express our T in terms of R too, which gives:

$\frac{S}{T} = \frac{2\cdot 4\pi R^3 \cdot 3\sqrt{3}}{3\cdot 4^3 R^3} = \frac{\sqrt{3}\pi}{8} \approx 68\%$

That is, using body centered cubic packing (picture c), we use up about 68% of the available space. Equivalently, we thus waste 32%.

Packing Factor for Face Centered Cubic

Looking at the blue balls in picture b, we see that there's 6 of them (four on the sides, one on top and bottom). Each is half a ball, so this gives 3 balls. We get one more ball by putting together the 8 corner pieces, for a total of 4 balls. Thus:

$S = 4\cdot \frac{4\pi R^3}{3}$

The relationship between T and R may however have changed, as we are no longer centering around a specific ball. This time, going from one corner to another (D above) won't work since there are gaps in between the balls when doing so (this can be seen in the picture). However, looking at one side, we see that the side diagonal crosses a length of 4R (with no gaps), and this length is also $\sqrt{2}L$. We thus get:

$\frac{S}{T} = \frac{4\cdot 4\pi R^3 \cdot 2 \sqrt{2}}{3 \cdot 4^3 R^3} = \frac{\sqrt{2}\pi}{6} \approx 74\%$

Face centered packing is thus more compact than body centered (as the picture suggests), using 6% more of the space.

Can we do even better?

There are other ways of packing which gives the 74% above, but are there even better ways?
Kepler postulated that the answer should be no, and there is a computer generated proof (a proof by exhaustion) that this is impossible: Hales' proof. Thus the answer is no, except that mathematicians are somewhat suspicious of the proof given the prevalence of bugs in computer code (the non-computer parts of the proof are considered reliable).

So to answer: almost surely not.

How do you estimate the number of candies in a jar?

Ignoring more intrusive methods, such as weighting the jar or x-raying the bottle and counting each candy, we obtain a way based on packing factors:
1. Estimate the volume of the jar
2. Estimate the percentage of the jar that is filled with candies (the packing factor defined above)
3. This gives the volume of candies. Divide that volume by the estimated volume of one candy.
You may be tempted to use the 74% above as your packing factor in step 2, but this is in fact not usually the right thing to do, because there's no guarantee that pouring down (round) candies into a jar will give a perfect packing. In fact, it isn't so: simply pouring down balls will give a packing factor of around 64%, that is, closer to something like the body rather than face centered packing. So it is 64% you should use as your packing factor - under the reasonable assumption that candies were simply poured into the jar, as opposed to, say, carefully put into their optimal position one by one.

Also, if the candies are not round, the packing factor may be somewhat altered. The exact mathematics easily becomes forbiddingly complex (say for teddybear shaped candies), so you're left with two choices: use the approximation 64% (perhaps adjusted according to some reasonable logic), or buy the same jar, fill it with the same candy, pour out all the candies again, and count them.