previous problem next problem
Cutting up rectangles
A rectangle is divided in n·m squares of equal size, like a matrix with n rows and m columns. By straight cuts from border to border, along the sides of the squares, the rectangle shall be completely cut up, leaving n·m separate squares. The following picture shows for n = 4 and m = 6 the start and the end of the procedure and in the middle a possible situation after several cuts.
We want to determine the minimum number of cuts. Two different ways of cutting will be discussed:
A : It is not allowed to cut through more than one piece at a time. (Pieces may not be stacked or laid alongside each other before cutting.)
B : Before each cut pieces may be stacked or laid alongside each other, allowing cuts through more than one piece.
The following picture shows three pieces in a stack:
This cut (red) is legal in variant B , not in variant A .
If you happen to have the right idea for variant A you will easily find the solution, without any computation. But you can also find the solution by testing the possible ways to cut up small rectangles; the rule for determining the minimum number of cuts will become evident.
Concerning variant B only this shall here be said: The intuitive idea for fastest cutting is the best one.