        \problemdata       % Takes 5 *mandatory* arguments
        {chocbar-mn}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS2-6} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
We are given a chocolate bar with $m \times n$ squares of
chocolate, and our task is to divide it into $mn$ individual squares.  We
are only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.

\begin{problemparts} \problempart Use strong induction to conclude the following:
\begin{theorem*}
To divide up a chocolate bar with $m \times n$ squares, we need at
most $m n - 1$ splits.
\end{theorem*}

\solution{This theorem does not immediately lend itself to an induction
proof, since there are two variables.  In general, propositions involving
several natural-valued variables can often be proved by using a sort of
nested induction.  However, in this case, we can get by with a
single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}
}

\problempart The theorem proves that \emph{at most} $mn - 1$
splits are needed to divide up an $m$ by $n$ chocolate bar.  Could you do
better?

\solution{The proof really shows that exactly $s - 1$ splits are
needed.  Observe that in the induction step, no matter how we split the
bar into smaller bars of size $p$ and $q$, exactly $(p - 1) + (q - 1) = s
- 1$ splits are required.}
\end{problemparts}

\end{problem}