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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Are m,and n allowed to have a common factor? $\endgroup$– Vassilis ParassidisMay 17, 2020 at 23:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If I can fold the piece of paper, this can be done in two cuts. Fold the paper at all of the vertical half-grid lines (lines halfway between the grid lines) accordion-style, and all of the vertical cuts can be made in one go. Then do the same type of accordion fold on each of the resulting strips to line up the horizontal grid lines, stack and cut again. A real topologist could probably get this down to one cut.
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.
This is the crux: no matter how you cut the remaining pieces, you are alway left with a piece that needs an extra vertical cut and an extra horizontal cut. After you've made the cuts as efficiently as possible. When you come down to making the extras, you have a piece that needs both a vertical and horizontal cut, and these two cuts cannot be made simultaneously. Thus you end up rounding both logs up independently.
answered May 18, 2020 at 1:06
-
$\begingroup$ What about for e.g. 5 by 5, where $\lceil\log_2m\rceil+\lceil\log_2n\rceil=6$ but $2^5>mn$? $\endgroup$ May 18, 2020 at 8:43