4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Wow this is incredible haha. Many thanks. I never had an experience of proving something of this kind before. $\endgroup$
    – Shorty
    Nov 12 '13 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.