Chocolate Bar

Each cut increases the number of pieces by 1. To get from 1 piece to 6 pieces requires exactly 5 cuts.

This problem can be generalized for an $m \times n$ bar of chocolate, where $m, n$ are positive integers. We shall prove that if we follow the procedure given in the problem, it will always require exactly $mn - 1$ cuts to break the $m \times n$ bar of chocolate into $1 \times 1$ pieces.

The quick way to prove this is to use Stephen's observation: whenever we cut, we always increase the number of pieces by 1. In this scenario, we call the number of pieces of chocolate a monovariant , since it increases by a set amount each time a cut is made. Thus, in order to get exactly $k$ pieces of chocolate, we must perform $k - 1$ cuts. Plugging in $k = mn$ gives our desired result.

Alternatively, we can use strong induction to prove our assertion. Let $C(m, n)$ be the number of cuts necessary to break a $m \times n$ bar of chocolate into $1 \times 1$ squares. For our base case, $C(1, 1) = 0,$ since a $1 \times 1$ piece of chocolate is already broken up as much as it can be. Since $0 = 1(1) - 1,$ our base case is proven.

For the inductive step, first let $x, y$ be some positive integers. Suppose the assertion that $C(m, n) = mn - 1$ holds for all positive integers $m < x$ and $n < y.$ Now, consider an $x \times y$ bar of chocolate. We can cut this into two pieces with dimensions $x_1 \times y$ and $x_2 \times y,$ where $x_1, x_2$ are positive integers such that $x_1 + x_2 = x.$ By the inductive step, it would take $x_1y - 1$ and $x_2y - 1$ cuts to break the two bars into $1 \times 1$ squares. Adding on the first cut, we get,

$C(x, y) = 1 + (x_1y - 1) + (x_2y - 1) = (x_1 + x_2)y - 1 = xy - 1.$

If instead we cut the bar into two pieces with dimensions $x \times y_1$ and $x \times y_2,$ with $y_1 + y_2 = y,$ then a similar result can be derived.

Thus, our inductive step is complete, so it will take $C(m, n) = mn - 1$ cuts to completely cut an $m \times n$ bar of chocolate into $1 \times 1$ squares. In the case of this problem, it will always take $2(3) - 1 = 5$ cuts to break up the bar, no matter how we make the cuts. $\blacksquare$