21
$\begingroup$

For each of these two questions, one can assume that the arrangements are polycubes (for which a definition can be found in the excerpt-image below).

Question A. How does one arrange $n$ unit cubes to minimize surface area?

Question B. How does one arrange $n$ unit cubes to form a rectangular prism of minimal surface area?

Various curricular materials discuss this problem for a specific number of cubes, but I have not seen the general case broached. For an example of an exploration at the pre-secondary level, see this instructional plan from the National Council of Teachers of Mathematics. A recent example of the problem posed in generality can be found on this math education blog-post as well as here.

My own attempt at combing the literature did not produce anything of import. From the two dimensional perspective, I see a question in a somewhat similar vein on MSE about unit squares, and another 2D question on MO, but neither seems applicable to the questions above.

Moreover, there are some related results (recently relayed to me by a geometer-mathematician) in:

Williams, W., & Thompson, C. (2008). The Perimeter of a Polyomino and the Surface Area of a Polycube. The College Mathematics Journal, 233-237.

For example, see the excerpt below:

enter image description here

One might also check the OEIS sequence recommended by Robert Israel (or found by googling), though I cannot vouch for its validity (cf. e.g. the remarks of its contributor here).

Non-trivial bounds, algorithmic approaches, or other relevant remarks are all welcome!

$\endgroup$
11
  • $\begingroup$ About question B. Should it be a perfect (discrete) rectangular prism of the form $T\times I$, or nearly perfect? Perhaps a penalty can be introduced for each imperfectness (to be still defined in one way or another). $\endgroup$ – Włodzimierz Holsztyński Aug 25 '14 at 19:12
  • 1
    $\begingroup$ @StevenStadnicki Wouldn't the continuous limit be upset by a similar phenomenon as occurs in the well-known example of the limit of a diagonal staircase function, as the step sizes become small? That is, in that case, the length of the staircase doesn't change as one makes the steps smaller, and so their is no advantage to following the diagonal with small steps. I would expect something similar here with the cubes... $\endgroup$ – Joel David Hamkins Aug 28 '14 at 1:06
  • 2
    $\begingroup$ A (very) specific question is: For $n=m^3+k^3$, $m \ge k$, is stacking one cube on another ever optimal? I think the answer is No unless $k=1$. $\endgroup$ – Joseph O'Rourke Aug 28 '14 at 11:24
  • 2
    $\begingroup$ Do the cube vertices have to be aligned to the unit grid in your questions, or one can put centres of 3 cubes at (0,0,0), (1,0,0), (0.5,1,0) for example? $\endgroup$ – Michael Aug 28 '14 at 16:30
  • 1
    $\begingroup$ Thanks for drawing this to my attention. I'll look if I get some time. $\endgroup$ – Lucia Apr 7 '20 at 6:19
12
+50
$\begingroup$

One geometric remark (which is reminiscent of a symmetrization principle used in isoperimetric problems): a minimizing polycube may be chosen to lie in the first octant, with three sides tangent to the coordinate planes, and so that the number of cubes in each column is monotonic in each coordinate, like a lozenge tiling:

enter image description here

The point is that you can choose some direction to be the surface of the earth, and let gravity pull all of the cubes down. This does not increase the surface area: the result ends up with at most one bottom and top face in each column. In adjacent columns of height $m$ and $n$, the number of exposed faces is at least $|m-n|$, which is minimized when they are sitting flush. Repeat this in each direction, until the configuration is monotonic (like a 3-dimensional Young diagram, but I don't know if there's a mathematical label).

Added: This argument gives an interpretation for the desired minimization problem. One has a sequence of Young diagrams in three directions such that the total number of squares adds up to $n$, and which are monotonic in the number of squares in each diagram (with some compatibility conditions). Let the number of squares in the young diagram adjacent to each coordinate plane be $x_1, y_1, z_1$ respectively. Then the surface area is $2(x_1+y_1+z_1)$. This is counting twice the number of blue, red, and green squares (excluding the corners) in the picture (pictured are the top squares, to which there is a corresponding bottom square in each column). We have $x_1\geq x_2 \geq \cdots \geq x_k$, and $x_1+x_2+\cdots+x_k=n$, and corresponding formulae for $y_i$ and $z_i$ counting the number of squares in each tableau parallel to a given coordinate plane. It shouldn't be too hard to solve this combinatorial optimization problem, but I don't have time to work it out now.

Addendum 2: I think I can describe the optimal solution, but I don't have time to write down the complete argument now.

It is helpful to consider the 2-dimensional case of Young diagrams. A length $n$ Young diagram is a sequence $x_1\geq x_2 \geq \cdots \geq x_{y_1}$, such that $\sum x_j=n$.

A 5,4,1 Young diagram

The dual diagram is $y_1 \geq y_2 \geq \cdots y_{x_1}$, where $y_i=\max\{ j | x_j\geq i\}$. The length of the boundary is $2(x_1+y_1)$. Then the symmetrization principle says that the minimal "polysquare" is a Young diagram. Let $P(2k)$ be the maximal size of a diagram with perimeter $2k$ (the "isoperimetric function"). Since a Young diagram fits inside a rectangle of sides $x_1, y_1$ with the same perimeter, clearly $P(2k) = \max_{a+b=k} ab = \lfloor \frac{k}{2} \rfloor \lceil \frac{k}{2}\rceil$. Also, the Young diagram which minimizes perimeter for a given $n$ clearly has $P(2(x_1+y_1-1))< n \leq P(2(x_1+y_1))$. Let $k=x_1+y_1$. Then the minimal perimeter will be realized by a Young diagram which, if $k$ is even, is a $k/2(k/2-1)$ rectangle with a row of $n-k(k-2)/4$ squares added on (so fitting in a $(k/2)^2$ square and containing a $k/2(k/2-1)$ rectangle). If $k$ is odd, then the Young diagram will be obtained from an $((k-1)/2)^2$ square with a row of $n-(k-1)^2/4$ squares added (so containing a $(k-1)/2\times (k-1)/2$ square, and contained in a rectangle of size $(k-1)/2\times (k+1)/2$). Note: The perimeter minimizer is far from unique. For example, if $n=8$, then the minimizer will be realized by the Young sequences $3,3,2$ and $4,4$. We are only describing a preferred choice of minimizers.

Now we may use this description of perimeter minimizing Young diagrams to describe minimal 3-D Young diagrams. As described above, we have a monotonic sequence of Young diagrams, each fitting inside the other, of sizes $x_1\geq x_2 \geq \cdots \geq x_k$. Then one checks that the perimeter is $2x_1$ plus twice the sums of the perimeters of the Young diagrams. Replace each Young diagram with a perimeter-minimizing one described above (one may observe that the choices are nested for $x_i \geq x_{i+1}$). Repeat this in the $y-$ and $z-$ directions to obtain a 3-D Young diagram in which the cross sections are perimeter minimizing 2-D Young diagrams. Then the 3-D Young diagram fits into an $a\times b \times c$ box, with $a\leq b\leq c$, and $|c-a|=1$ (so $b= a$ or $c$). A similar isoperimetric argument to the above implies that it contains an $a^3$ cube and is contained in a $c^3$ cube, where $a=\lfloor n^{1/3} \rfloor$. If $ n < a^2(a+1)$, then it is obtained from an $a^3$ cube with a $n-a^3$ optimal Young diagram attached to one face. If $a^2(a+1)\leq n < a(a+1)^2$, then it is obtained from an $a^2\times (a+1)$ box by attaching an optimal $n-a^2(a+1)$ Young diagram to an $a\times (a+1)$ face. And if $a(a+1)^2 \leq n$, then it is obtained from an $a\times (a+1)^2$ box by attaching an $n-a(a+1)^2$ Young diagram to an $(a+1)^2$ face. Again, these are not the unique perimeter minimizers, but a description of optimal ones. It's possible that I've made a mistake, but at least the symmetrization principles underlying the argument seem solid.

$\endgroup$
4
  • $\begingroup$ For my own clarification (paragraph after the diagram): Given an $n$, is there an obvious way to compute $k$? I will write out my understanding so that you can tell me where I've gone wrong! In your example, $n = 8$, so the $\max$ formula for $P(2k)$ suggests making $\frac{k}{2} = 3$ will be a good idea, i.e., so that $n = 8 \leq 9$. Indeed, this value of $k=6$ satisfies the given inequality, and (since $n=8$ is even) we make a $6/2 \times (6/2 - 1) = 3 \times 2$ rectangle with a row of $8 - 6(6-2)/4 = 2$ squares added on, for the (non-unique but optimal) Young sequence $3,3,2$. $\endgroup$ – Benjamin Dickman Sep 3 '14 at 6:46
  • $\begingroup$ Yes, let $m^2 < n\leq (m+1)^2$. If $n\leq m(m+1)$,then $k=2m+1$,and if $m(m+1) < n$,then $k=2m+2$. $\endgroup$ – Ian Agol Sep 3 '14 at 16:50
  • $\begingroup$ It will take me some time to try and make sense of your last paragraph (I had not seen Young diagrams before, and "isoperimetric arguments" are not presently in my arsenal!). (1) Do you have any suggestions for what I might read to be able to grasp the last paragraph? (2) Do you see any way to modify your response to Question A so as to make sense of Question B? (Or perhaps B should be tackled using a more number theoretical approach instead of a geometric one?) $\endgroup$ – Benjamin Dickman Sep 8 '14 at 2:05
  • $\begingroup$ @BenjaminDickman: I'm not sure what a rectangular prism is. $\endgroup$ – Ian Agol Sep 8 '14 at 2:12
8
$\begingroup$

If you suppose that the cubes are shifted compared to each other by integers vectors (which might be not hard to prove), then a problem practically equivalent to Question A was solved by Bollobas and Leader in general for $d$ dimensions: http://link.springer.com/article/10.1007%2FBF01275667

There original problem was the following. The graph $G_d(k)$ has $k^d$ vertices which are associated to the points of a $d$-dimensional cubical grid of side length $k$ and the edges are given by the neighbors, e.g., every vertex not on a side has $2d$ neighbors. The edge neighborhood of a vertex set $S$ is the number of edges between $S$ and $V(G_d(k))\setminus S$. Determine the smallest possible neighborhood of $n$ vertices.

They have proved that it is (a) best solution to take the first $n$ unit cubes in the ``cubical order'' which is exactly the order how anyone would define it given the name - you want as few of the maximal valued coordinates as possible. Notice that their edge neighborhood would be exactly the area of the surface if the cubes were not on the boundary. The family about which they prove that it is extremal is shifted to the boundaries and is stair-convex, so its edge-boundary is exactly twice its surface. I don't see why their theorem rules out that another family could have a smaller surface, but their proof method (applying shifts) should work for this problem as well.

$\endgroup$
0
5
$\begingroup$

Not an answer, just an example that might provide some intuition. $n{=}9$:


  CubesVol9


$\endgroup$
5
  • 1
    $\begingroup$ Isn't the second one a 10? $\endgroup$ – Dror Bar-Natan Aug 28 '14 at 0:26
  • $\begingroup$ Oh, you are right, I was exploring several $n$. Will fix. Thanks! $\endgroup$ – Joseph O'Rourke Aug 28 '14 at 1:01
  • 2
    $\begingroup$ My intuition is not much better than "try to make a cube," and so I'm not surprised to see the minimal arrangement depicted above for $2^3 + 1$. As noted in the question, it is often explored for specific cases (e.g., $n = 9$) at the pre-secondary level; but I have no good idea(s) for how to approach the general case. $\endgroup$ – Benjamin Dickman Aug 28 '14 at 1:46
  • $\begingroup$ (If you are up for making another image: It would be great to see an example worked out using the approach described by Ian Agol...!) $\endgroup$ – Benjamin Dickman Sep 3 '14 at 7:21
  • 1
    $\begingroup$ @BenjaminDickman: That's a good idea. Maybe eventually, but no time now... $\endgroup$ – Joseph O'Rourke Sep 4 '14 at 11:50
3
$\begingroup$

Here are some ideas about the related question: for fixed $k$, how many cubes can you arrange while keeping the surface area $\leq k$?

  1. If the surface of an arrangement contains three or more sides of a cube not in the arrangement, then it is not optimal, because we can add that cube without increasing surface area.
  2. An optimal arrangement cannot have a hole (i.e., it cannot separate $\mathbb{R}^3$). If it did, we could fill it in, reducing the surface area and increasing the number of cubes.
  3. Choose a direction (parallel to an edge), and think of the arrangement as a stack of planar arrangements. Conjecture: if the arrangement is optimal, each of these sections is a rectangle (or can be reorganized to such a form).
  4. Conjecture: An optimal arrangement that is a stack of rectangles can be reorganized to a shape of one of three special forms: (a) A cube with a rectangle on one side (not sticking out); (2) an $m \times m \times (m+1)$ solid with a rectangle on one side; (3) an $m \times (m+1) \times (m+1)$ solid with a rectangle on one side.

Assuming the conjectures, you can find the optimal arrangement for $n$ cubes (if there is one) by finding $m$ such that $m^3 \leq n < (m+1)^3$, then looking at $n - m^3$.

  • If $n-m^3 \leq m^2$, write $x = n-m^3$ and factor $x = ab$ so that there is no divisor $d$ of $x$ with $a< d< b$. The area would be $A_1(a,b) = 6m^2 + 2(a+b)$.
  • If $m^2 < n-m^3 \leq 2m^2+m$, write $y = (n-m^3) - m^2(m+1)$, factor $y = ab$ so that there is no divisor $d$ of $y$ with $a< d< b$.
    The area would be $A_2(a,b) = (6m^2 + 4m) + 2(a+b)$.
  • If $2m^2+m < n-m^3$, write $z = (n-m^3) - (2n^2+n)$, factor $y = ab$ so that there is no divisor $d$ of $y$ with $a< d< b$. The area would be $A_3(a,b) = (6m^2 + 8m+2) + 2(a+b)$.

The case of $n= 11$ cubes is instructive. The algorithm here says that you need to put a rectangle with area $3$ onto a $2\times 2\times 2$ cube, which cannot be done. If you attempt to put three cubes on one face of the $2\times 2\times 2$ cube, you see that you can improve the arrangement to $12$ cubes without increasing area.

$\endgroup$
2
$\begingroup$

A question fairly close to Question B was studied in [1] (JSTOR link here), which finds the choices of $n$ such that some volume-$n$ integer-side-length rectangular prism minimizes the volume/surface area ratio among all integer-side-length rectangular prisms with volume at most $n$.
Note, however, that on p. 194, Alspaugh notes that his/her method doesn't actually find the factorization $n = xyz$ that is optimal, and gives good examples of where the easy conjectures fail. Still, this should give you some bounds on the optimal volume/surface area ratio.

[1] S. Alspaugh, "Farmer Ted goes 3D," Math. Magazine 78(3), June 2005, pp. 192-204. DOI: 10.2307/30044156

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.