# Cutting a Rectangular Board

There is an $$m \times n$$ rectangular board drawn on a graph paper. You need to cut it into $$mn$$ $$1 \times 1$$ squares by straight cuts along the grid lines. You are allowed to stack several pieces together to cut them at the same time, which is considered one cut. Design a technique that performs this task with the minimum number of cuts.

• Are m,and n allowed to have a common factor? May 17 '20 at 23:51

If I cannot fold the paper, then the best you can do is $$\lceil \log_2 m \rceil + \lceil \log_2 n \rceil$$. At each stage, simply cut all pieces that are not already $$1\times1$$ as close to "in half" as possible (perfectly if length/width is an even number of blocks, a grid line next to the centerline if an odd number of blocks).
It's not a formal proof, but it's pretty easy to see you can't do any better by noting that after $$k$$ cuts, the most number of pieces you can have is $$2^k$$. So you have to perform at least a number of cuts $$k$$ such that $$2^k \geq mn$$, which is exactly the sum of logarithms above.
Edit: @EspeciallyLime makes a good point in the comment below, but I think my logic still holds. Let's use the $$5 \times 5$$ grid as an example. The first cut can either break the grid into a $$1 \times 5$$ strip and a $$4 \times 5$$ strip, or $$2 \times 5$$ and a $$3 \times 5$$. Either way, one of the remaining pieces still needs 2 vertical cuts to be completely separated, and we still need 3 horizontal cuts.
• What about for e.g. 5 by 5, where $\lceil\log_2m\rceil+\lceil\log_2n\rceil=6$ but $2^5>mn$? May 18 '20 at 8:43