A carpenter has a rectangular board, $x$ feet long and $y$ feet wide, with total area $n = xy
$square feet. The board is to be divided into n squares (each 1 foot x 1 foot) by successively
cutting a rectangle into two smaller rectangles whose sides are each a whole number of feet.
Using strong induction, show that exactly $n -1$ cuts are needed, no matter how the carpenter decides to perform the cuts.
Any help please? I was thinking of maybe trying to write down the possible number of arrangements he can do it but I think it is pointless since it states no matter how it is done.
Best Answer
Suppose the result is true for all $m\lt n$. We show the result is true for $n$. One cut divides the board into two rectangles of area $a$ and $b$ where $a+b=n$, and $a,b\lt n$. By the induction hypothesis, it takes exactly $a-1$ cuts to split the board of area $a$ into $1\times 1$'s, and exactly $b-1$ to split the board of area $b$ into $1\times 1$'s, for a total of $1+(a-1)+(b-1)=n-1$.