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.

  • How confident are you in answering "No"? That is, what have you tried? – Xoque55 Jul 28 '15 at 10:30
  • @Khosrotash Rather, it seems not impossible. For just because the volumes are the same, it is easy to find examples that don't work: Can you fit a $6 \times 1 \times 1$ box in a space of $2 \times 3 \times 1$? No, however we have $2*3*1 = 6$ cubic units and $6*1*1 = 6$ cubic units also. – Xoque55 Jul 28 '15 at 10:33
  • yes you are right , when I think twice ,i get your point – Khosrotash Jul 28 '15 at 10:34
  • I am just trying to figure out an equation of some sorts to show that it is not possible – DoubleOseven Jul 28 '15 at 10:57

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

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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