Problem of the Month (September 2003)

A polycube is a collection of unit cubes glued together along entire faces. We are interested this month in pairwise touching collections of polycubes: a set of polycubes each pair of which touch along a face of at least one cube. For example, here is a set of 6 polycubes contained in a 2×3×4 box that are pairwise touching:

We show some space between the cubes so you can see between them. Another way to represent the same diagram is in layers:

Can you find 5 pairwise touching polycubes that will fit inside an 2x3x3 box? 8 inside a 4×4×4 box? What's the largest number of pairwise touching polycubes that will fit inside an a×b×c box? Can you prove any upper or lower bounds?

ANSWERS

Let Z(a,b,c) denote the largest number of pairwise touching polycubes inside a a×b×c box. Jeremy Galvagni, Gyozo Nagy, and Joseph DeVincentis confirmed that Z(2,3,3)≥5 and Z(4,4,4)≥8.

Paul Kahler improved the lower bound for Z(2,5,5), showing that it was at least 8.

Gyozo Nagy (after single-handedly saved the Hungarian oil industry by plugging back a power cord into a switch) was the first to prove that Z is unbounded. He does this by packing an a×b×(ab/2) box with ab/2 pairwise touching polycubes. Mark Michell improved this by finding n+1 polycubes in a n×(n+1)×2 box. Joseph DeVincentis improved this further by finding n+2 pairwise touching polycubes in a n×n×2 box, as the example below demonstrates:

177xxx   188xxx
1277xx   2288xx
12377x   33388x
123477   444488
123457   555558
123456   666666

Joseph DeVincentis also packed n+3 polycubes into an n×n×3 box, and n+4 polycubes into an nxnx4 box.

Trevor Green, Joseph DeVincentis, and Mark Michell noted that Z(a,b,1)≤4 (because of the 4 color theorem). Trevor Green also notes Z(a,2,1)≤3 and Z(a,1,1)≤2, and Z is clearly non-decreasing in every variable and symmetric.

Trevor Green proved that Z(a,b,c)≤ab+1, and therefore is eventually constant as a function of c. His proof: slice perpendicular to the c axis at the lowest place possible so that some polycube P is entirely below the cut. Suppose this polycube has k faces along the cut. There can be no more than ab-k+1 polycubes below the cut, since each must touch the face right below the cut, and there can be no more than k polycubes right above the cut since each must touch P.

Jeremy Galvagni noted that in an a×b×c box there are ab(c–1)+a(b–1)c+(a–1)bc = 3abc–ab–ac–bc boundaries between individual cubes, but n pairwise connected polycubes will require at least n(n-1)/2 regional boundaries, so we must have Z(a,b,c) < 1+√(6abc–2ab–2ac–2bc). Sasha Ravsky improved this slightly noting that abc-n boundaries are necessary to hold the polycubes together, so we get Z(a,b,c) < 2+√(4abc–2ab–2ac–2bc).

Jeremy Galvagni asked the reverse question than I did: what is the smallest volume box that will contain n pairwise-touching polycubes? The answers:

n	box
1	1×1×1
2	1×1×2
3	1×2×2
4	2×2×2
5	2×3×3
6	2×3×4
7	2×4×4
8	3×4×4

Here are the known bounds on Z(a,b,c). Pairs of numbers indicate lower and upper bounds.

a × b × 1 Box

a \ b	1	2	3	4	5
1	1	2	2	2	2
2	2	3	3	3	3
3	2	3	4	4	4
4	2	3	4	4	4
5	2	3	4	4	4

a × b × 2 Box

a \ b	1	2	3	4	5
1	2	3	3	3	3
2	3	4	4	4	4
3	3	4	5	6	6
4	3	4	6	7	7,8
5	3	4	6	7,8	8,10

a × b × 3 Box

a \ b	1	2	3	4	5
1	2	3	4	4	4
2	3	4	5	6	6
3	4	5	5	6	7
4	4	6	6	8	8,10
5	4	6	7	8,10	9,13

a × b × 4 Box

a \ b	1	2	3	4	5
1	2	3	4	4	4
2	3	4	6	7	7,8
3	4	6	6	8	8,12
4	4	7	8	9,12	9,16
5	4	7,8	8,12	9,16	10,18

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 9/11/03.