1.
Consider the following puzzle:
You have a rectangular chocolate bar, made up of \(n\) identical squares of chocolate. You can take such a bar and break it along any row or column. How many times will you have to break the bar to reduce it to \(n\) single chocolate squares?
At first, this question might seem impossible. Perhaps we meant to ask for the smallest number of breaks needed. Let’s investigate.
(a)
Suppose you started with a \(1\times 3\) bar. How many breaks would you need to reduce it to single squares?
(b)
If you had a \(1\times 4\) bar, how many breaks are required?
If you had 4 squares arranged in a \(2\times 2\) square, your first break would require you to break the chocolate into two \(1 \times 2\) bars. Then each of these would require more break(s), for a total of more break(s), for a total of breaks to go from the \(2\times 2\) to single squares.
(c)
A \(6\)-square bar could either be a \(1 \times 6\) bar, requiring breaks, or a \(2 \times 3\) bar.
There are two ways to proceed now.
- Break the bar into two \(1 \times 3\) bars, each requiring more breaks, for a total of breaks.
- Break the bar into a \(1\times 2\) bar and a \(2 \times 2\) bar. The \(1 \times 2\) bar takes more break(s) and the \(2 \times 2\) bar takes more break(s), for a total of breaks.
(d)
Based on the above data, what should our conjecture for the number of breaks to reduce an \(n\)-square bar to single squares, in terms of \(n\text{?}\)
It will take breaks to reduce an \(n\)-square bar to single squares.
(e)
Do we believe this? Suppose you used one break to reduce the bar into two smaller bars, with \(a\) and \(b\) squares respectively. If the conjecture is correct, how many more breaks will it take to reduce the size \(a\) bar?
How many more breaks will it take to reduce the size \(b\) bar?
All together, including the initial break, this is, in terms of \(a\) and \(b\)
But what is \(a+b\text{?}\) We got \(a\) and \(b\) by breaking the \(n\) squares in two pieces, so \(a+b =\). This gives us a total number of breaks as .
