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 2x3x4 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 4x4x4 box? What's the largest number of pairwise touching polycubes that will fit inside an a x b x 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 axbxc 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 powercord into a switch) was the first to prove that Z is unbounded. He does this by packing an axbx(ab/2) box with ab/2 pairwise touching polycubes. Mark Michell improved this by finding n+1 polycubes in a nx(n+1)x2 box. Joseph DeVincentis improved this further by finding n+2 pairwise touching polycubes in a nxnx2 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 nxnx3 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 axbxc 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:

nbox
11x1x1
21x1x2
31x2x2
42x2x2
52x3x3
62x3x4
72x4x4
83x4x4

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

a x b x 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 x b x 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 x b x 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 x b x 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.