Equal division of unit square tiles without stacking into individual tiles

1.4k Views Asked by At

A chocolate bar having (m X n) unit square tiles is given. How many number of cuts would be needed to break it completely, without stacking, into individual tiles.

  1. (m X n)
  2. (m-1) X (n-1)
  3. (m X n) - 1
  4. (m X n)+ 1
2

There are 2 best solutions below

0
On

The answer is $(m-1)+(n-1)$: Since you have $m$ rows, you have $m-1$ connections between them.same goes for $n$ columns. Therefore you have to make $(m-1)+(n-1)$ breaks in the chocolate.

0
On

Answer is $m * n-1$.

But your question needs a clarification on that a "Cut" is counted as 1 only when the component you are cutting is fully connected. So once you cut 1st row in one cut, and you have 2 different grid one of 1*n and another $(m-1)*n$.

now for each $1 * n$ grid u need n-1 cut (and there are total m rows), and breaking an m*n grid into m different 1*n grid is m-1 cuts. so all in all, it is $(n-1)*m + m-1 = n*m -1$.