Manfred BörgensMathematical Problems |
problem list previous problem | main page |

deutsche Version |

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

Solution

last update 2008-01-21

previous problem | problem list

Manfred Börgens | main page