4

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.

Shorty
  • 467

1 Answers1

3

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

André Nicolas
  • 507,029
  • Wow this is incredible haha. Many thanks. I never had an experience of proving something of this kind before. – Shorty Nov 12 '13 at 01:03