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?

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 | 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 | 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 | 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 | 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.