# Standardized test problem: Packing spheres into a rectangular prism

So, this was a problem in the new standardized high school tests California has started using(CAASP). These new tests are completely done on the computer, and feature what they call Computer Adaptive Testing. Basically, the test "adapts" to how the student is doing, and offers harder or easier problems based on it.

However, this problem appeared as the second to last question, and was extremely tricky. I'm curious as to how one is supposed to do this problem.

How many spheres with diameter $3$ can one fit into a rectangular prism with dimensions $24.1$, $30.1$, and $16.9$?

If anybody needs any clarifications, I'll try to be fairly prompt.

Thanks

• As this appears to be a question from the California standardized tests (CAASPP) for the current school year, and as there is no set state-wise date for the administration of these tests, this question will remain locked until the end of the school year (which appears to be about Jun 16). – user642796 Apr 22 '15 at 2:59
• This appears to be a terrible standardized question. The general sphere packing problem is very difficult. – Peter Woolfitt Jun 17 '15 at 8:48
• It's the first test I've taken with the new CORE requirements. They say that the test adjusts its difficulty depending on how well one does, and this was the second to last question. I thought it was awfully hard, and was curious if there was a somewhat easier way to do it. – horace he Jun 18 '15 at 15:15
• You must be good at math ;) the test apparently decided it was "done" with your winning streak so it threw an open problem at you. That's slightly less blatant than asking whether or not the Reimann hypothesis is true. – Zach466920 Jun 26 '15 at 20:14
• @Zach466920 Hah. I wish I was that good. The rest of the problems on this test were your standard standardized math problems, and then all of a sudden this problem comes out. To be honest, I have a bit of a suspicion that the problem makers didn't completely understand this problem, considering its out of place difficulty level compared to the rest of the problems. – horace he Jun 28 '15 at 2:49

No proofs, just some simple observations and numerical experiments with the face-centered cubic (FCC) packing and hexagonal close-packing. The upshot is: $540$ balls (twelve layers of $45$ in the hexagonal close-packing) just fit into a box with the given dimensions.

Caveat: Except for the $540$-ball packing, the numerical claims below are not carefully hand-checked.

• Multiplying the volume of the box by the average density of the FCC packing and dividing by the volume of a ball of radius $3$ gives an absolute upper bound of $642$ balls.

• Let $\{d_{1}, d_{2}, d_{3}\} = \{16.9, 24.1, 30.1\}$, and let $\Lambda$ be the lattice containing the point $(\frac{3}{2}, \frac{3}{2}, \frac{3}{2})$ and generated by the vectors $v_{1} = (3, 0, 0)$, $v_{2} = (\frac{3}{2}, \frac{3}{2}\sqrt{3}, 0)$, and $v_{3} = (\frac{3}{2}, \frac{1}{2}\sqrt{3}, \sqrt{6})$. Counting the number of balls of diameter $3$ centered at points of $\Lambda$ and contained within the box $$[0, d_{1}] \times [0, d_{2}] \times [0, d_{3}]$$ gives: $$\begin{array}{cc} (d_{1}, d_{2}, d_{3}) & n \\ \hline (16.9, 24.1, 30.1) & 500 \\ (16.9, 30.1, 24.1) & 480 \\ (24.1, 16.9, 30.1) & 512 \\ (24.1, 30.1, 16.9) & 480 \\ (30.1, 16.9, 24.1) & 486 \\ (30.1, 24.1, 16.9) & 476 \\ \end{array}$$ The stereogram below shows the $512$-ball packing, with four layers of $38$ and $8$ layers of $45$.

• The preceding packing (in which every third layer is "inoptimally-placed") leads one to consider the hexagonal close-packing with the same two bottom layers. Indeed, this does a bit better: $$\begin{array}{cc} (d_{1}, d_{2}, d_{3}) & n \\ \hline (16.9, 24.1, 30.1) & 510 \\ (16.9, 30.1, 24.1) & 495 \\ (24.1, 16.9, 30.1) & 540 \\ (24.1, 30.1, 16.9) & 513 \\ (30.1, 16.9, 24.1) & 495 \\ (30.1, 24.1, 16.9) & 486 \\ \end{array}$$ Particularly, twelve layers of $45$ balls can be stacked into the box $[0, 24.1] \times [0, 16.9] \times [0, 30.1]$:

The smallest enclosing box (top view shown below) has dimensions $$24 \times \tfrac{15}{4}(1 + 2\sqrt{3}) \times 3(1 + 11\sqrt{\tfrac{2}{3}}) \approx 24 \times 16.75 \times 29.45,\quad \text{cf. } 24.1 \times 16.9 \times 30.1.$$

• Great answer! Thanks for taking the time. – Peter Woolfitt Jun 27 '15 at 14:11
• @PeterWoolfitt: Thank you for the bounty. :) With a question such as this (which, as you say, is terrible for a timed, standardized test), there's always the nagging suspicion of having overlooked some clever geometric idea. Still, I'll be surprised (albeit pleasantly) if there proves to be a denser packing.... – Andrew D. Hwang Jun 27 '15 at 15:46

The fact that $24.1$ and $30.1$ are just larger than multiples of $3$ makes me assume the problem writer expects you to make a lower layer that is a square pack of $8 \times 10$, then stack a $7 \times 9$ square pack on that, an $8 \times 10$ on that, and so on. The layer spacing of this packing is $\frac {\sqrt 2}23 \approx 2.121$, so we get $1+\lfloor \frac {16.9-3}{2.121}\rfloor=7$ layers in the box, for $80 \cdot 4 + 63 \cdot 3=509$. My theory is weakened by the fact that the vertical is not a tight fit. Of course, I have not proved that my packing is optimal, and in fact I strongly suspect it is not. Was that one of the choices? I agree this is a terrible problem for a timed test. Even making the third dimension $18.1$ and assuming a cubic pack would be better.

• It was a free response problem, so I can't check that for you unluckily. – horace he Jun 20 '15 at 16:21
• You can add 9 spheres to one of the 9x7 layers. Still $(1+2\sqrt 2+\sqrt 3)3<16.9$ – san Jun 21 '15 at 14:13