Building a box from smaller boxes

Question

John has 77 boxes each having dimensions 3x3x1. Is it possible for John to build one big box with dimensions 7x9x11?

I'm leaning towards no, but I would like others opinion.

Answer 1

The volume of the big box is $V_B = 7\cdot 9 \cdot 11 = 693$, the total volume of the small boxes is $V_b = 77 \cdot 3 \cdot 3 \cdot 1 = 693$.

This means the volume of the small boxes is sufficient and we need to use all small boxes.

Let us try to model this problem Tetris style:

• We have a base field, e.g. $7\times 9$, and need to drop all 77 small boxes over it.
• For each drop we have two decisions:
  • where to put the center of the box $c = (c_x, c_y, c_z)$ over the base field $(c_x, c_y) \in I_x \times I_y$ with $I_x = \{ 1, \ldots, 7 \}$ and $I_y = \{ 1, \ldots, 9 \}$
  • how to orientate the $3\times 3\times 1$ box. There seem only three feasible orientations:
    • a large $3\times 3$ side as base, like a pizza box ("O")
    • a small $3 \times 1$ side as base, orientated along the $x$-axis ("-")
    • a small $3 \times 1$ side as base, orientated along the $y$-axis ("|")
• We loose if after the drop some part of the box sticks outside the big volume
• We win if we dropped all $77$ boxes without loosing.

This is a search space of $77\times 7 \times 9 \times 3 = 14553$ drop configurations. Not that much for a machine.

We could avoid the drop simulation and instead have $c_z$ as another choice. This would enlarge the search space to $77\times 7 \times 9 \times 11 \times 3 = 160083$ configurations. In both cases we need to check that boxes do not intersect.

This should be sufficient to code a solver which visits all configurations of the search space (brute force) and will answer the question by either listing feasible configurations or reporting that there is no solution.

Note: I submitted this before MJD published a counter argument.

Answer 2

The answer is no; John can't even fill up the topmost $7\times 11\times 1$ slice of the $7\times 11\times 9$ box. Consider just the top $7\times 11$ face of this box; look just at this face and ignore the rest of the box. A solution to the problem would fill up this $7\times 11$ rectangle with large $3\times3$ rectangles and small $3\times 1$ rectangles. But $7\times 11$ is not a multiple of $3$.