 |
 |
Problem Posts |  |
 |
 |
Image Credit: "Cardboard Box City" by James Nash. Licensed under CC BY-NC-SA 2.0.
No, I don't think they'll make you solve this problem in fifteen seconds mentally. |
You may wonder why I used the P-word for something as "simple" as packing boxes. I mean, the question is straightforward... right?
THE PROBLEM
You have a big rectangular pallet upon which you must place identical rectangular boxes. You can't stack, collapse, or overlap boxes. The sides of the boxes have to parallel to one of the sides of the pallet. What's the maximum number of boxes you can place?
You have a big rectangular pallet upon which you must place identical rectangular boxes. You can't stack, collapse, or overlap boxes. The sides of the boxes have to parallel to one of the sides of the pallet. What's the maximum number of boxes you can place?
It's a familiar but unremarkable question, especially for many mathletes who've had to do it under time pressure. (Fifteen seconds mental? Easy!) And the real-life applications are obvious - putting things into shipping containers, for example.
Thing is, there's a problem with this problem. Usually you can drill students by giving them the same problem, but with different numbers. Not so for this one. Change the numbers ever so slightly, and you could effectively turn a fifteen-second exercise to a research-level Godzilla.
Let me demonstrate with three questions: one easy, one okay, and one difficult. Note that only difference is the numbers I put in.
Problem 1
QUESTION 1 (For the Young Ones)
You have a rectangular pallet that measures $42 \cm$ by $63 \cm$. You want to fill it with $7\cm$ by $7\cm$ boxes. How many can you place?
You have a rectangular pallet that measures $42 \cm$ by $63 \cm$. You want to fill it with $7\cm$ by $7\cm$ boxes. How many can you place?
So this part is the one even a toddler can do.
NAIVE SOLUTION 1.1 (Dividing Areas)
The area of the large box is $42\cm \times 63\cm = 2646\cm^2$. The area of each small box is $7\cm \times 7\cm = 49\cm^2$. Dividing, we get $2646\cm^2/49\cm^2= \boxed{54}$ boxes.
The area of the large box is $42\cm \times 63\cm = 2646\cm^2$. The area of each small box is $7\cm \times 7\cm = 49\cm^2$. Dividing, we get $2646\cm^2/49\cm^2= \boxed{54}$ boxes.
It's pretty clear that we just got lucky this time. Dividing areas only gives us the maximum number of boxes! Sure, you could probably fit all the boxes, but you may have to cut some up, like in the example. This second part demonstrates how this approach fails:
QUESTION 2 (Slightly Harder)
Same pallet as before, but now the boxes are $13 \cm$ by $11 \cm$. How many can you place?
Same pallet as before, but now the boxes are $13 \cm$ by $11 \cm$. How many can you place?
NAIVE "SOLUTION" 2.1 (Dividing Areas)
The area of the large box is $42\cm \times 63\cm = 2646\cm^2$. The area of each small box is $13\cm \times 11\cm = 143\cm^2$. Dividing, we get $2646\cm^2/143\cm^2\approx 18.503$. So you can fit $\boxed{18}$ boxes all in all, right?
The area of the large box is $42\cm \times 63\cm = 2646\cm^2$. The area of each small box is $13\cm \times 11\cm = 143\cm^2$. Dividing, we get $2646\cm^2/143\cm^2\approx 18.503$. So you can fit $\boxed{18}$ boxes all in all, right?
WRONG! Thing is, you can't fit eighteen boxes without having to cut some up. If you don't believe me, cut some pieces of paper to scale and experiment. It's starting to look like the only way to find out if everything fits is manual checking. But this problem comes up all the time in oral speed contests. What do we do? Well, from experience this method works very often:
NAIVE "SOLUTION" 2.2 (Rectangular Array - Supposedly Okay Method)
Assume the optimal packing is a rectangular array, i.e. we get the maximum if we neatly arrange the boxes in rows and columns. (truth is, this is a very BAD assumption!)
So we have two choices: We can align the long side of the boxes with the long side of the pallet, or we can align them with the short side of the pallet.
Case 1 (Long with Long). We have at most $42\cm / 11\cm \approx 3.8$ rows and at most $63\cm / 13\cm \approx 4.8$ columns. So we have a $3\times 4$ array with $\boxed{12}$ boxes.
Case 2 (Long with Short). We have at most $42\cm / 13\cm \approx 3.2$ rows and at most $63\cm / 11\cm \approx 5.7$ columns. So we have a $3\times 5$ array with $\boxed{15}$ boxes.
It's clear that Case 2 allows us to pack more boxes, so that's the answer we give. Is it the right answer?
Assume the optimal packing is a rectangular array, i.e. we get the maximum if we neatly arrange the boxes in rows and columns. (truth is, this is a very BAD assumption!)
So we have two choices: We can align the long side of the boxes with the long side of the pallet, or we can align them with the short side of the pallet.
Case 1 (Long with Long). We have at most $42\cm / 11\cm \approx 3.8$ rows and at most $63\cm / 13\cm \approx 4.8$ columns. So we have a $3\times 4$ array with $\boxed{12}$ boxes.
Case 2 (Long with Short). We have at most $42\cm / 13\cm \approx 3.2$ rows and at most $63\cm / 11\cm \approx 5.7$ columns. So we have a $3\times 5$ array with $\boxed{15}$ boxes.
It's clear that Case 2 allows us to pack more boxes, so that's the answer we give. Is it the right answer?
Surprisingly, yes, this would give the correct answer. But are we sure this method always works? NO.
QUESTION 3 (Whoa There!)
Same pallet as before, but now the boxes are $15 \cm$ by $11 \cm$. How many can you place?
Same pallet as before, but now the boxes are $15 \cm$ by $11 \cm$. How many can you place?
The box is just slightly longer than the one in Question 2; will our technique work?
Dividing volumes gives us $16$, so we can't have more than sixteen boxes. Assuming a rectangular array gives $12$, but the drawing shows a lot of space is wasted. So, what to do? Which is right?
 |
| You have fifteen seconds to find a more creative approach. |
I'll cut to the chase: Both are wrong.
ANSWER 3
By trial-and-error or luck (or a website) we find the following configuration of fifteen boxes (not unique). This is optimal because of the algorithm [1] used. That escalated quickly!
By trial-and-error or luck (or a website) we find the following configuration of fifteen boxes (not unique). This is optimal because of the algorithm [1] used. That escalated quickly!
But we don't have computer access during contests. When the box has just the right dimensions, this kind of problem escalates to a hopeless trial-and-error bash. We would be better off giving the Rectangular Array answer and hoping it's correct, or rather, it's what's on the Answer Key.
What is this telling us? Essentially, we're at the mercy of the problem setters. Barring the cases when dividing areas or Rectangular Array gives the right answer, there probably isn't any fast (human) way to find solutions, or to justify that they're optimal.
References
[1] E. G. Birgin, R. D. Lobato and R. Morabito. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. Journal of the Operational Research Society, volume 61, pp. 306-320, 2010.
Any interesting comment, or unorthodox variant problem? Do pop a comment!
No comments:
Post a Comment