1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ How confident are you in answering "No"? That is, what have you tried? $\endgroup$
    – Xoque55
    Commented Jul 28, 2015 at 10:30
  • $\begingroup$ @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. $\endgroup$
    – Xoque55
    Commented Jul 28, 2015 at 10:33
  • $\begingroup$ yes you are right , when I think twice ,i get your point $\endgroup$
    – Khosrotash
    Commented Jul 28, 2015 at 10:34
  • $\begingroup$ I am just trying to figure out an equation of some sorts to show that it is not possible $\endgroup$ Commented Jul 28, 2015 at 10:57

2 Answers 2

9
$\begingroup$

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

$\endgroup$
0
-2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .