\input{latex-macros/handout-preamble.tex}
\inhandout{
\decideaboutsolutions
\usesimpleproblems
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem starts here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
\PTAGfilename{CP0301_box_unstacking}
\PTAGhistory{S09_cp4t}
\PTAGkeywords{induction}
%
Here is another exciting 6.042 game that's surely about to sweep the
nation!

You begin with a stack of $n$ boxes.  Then you make a sequence of moves.
In each move, you divide one stack of boxes into two nonempty stacks.  The
game ends when you have $n$ stacks, each containing a single box.  You
earn points for each move; in particular, if you divide one stack of
height $a + b$ into two stacks with heights $a$ and $b$, then you score
$ab$ points for that move.  Your overall score is the sum of the points
that you earn for each move.  What strategy should you use to maximize
your total score?

As an example, suppose that we begin with a stack of $n = 10$ boxes.
Then the game might proceed as follows:
%
\[
\begin{array}{cccccccccccl}
\multicolumn{10}{c}{\textbf{Stack Heights}} & \quad & \textbf{Score} \\
\underline{10}&&&&&&&&& && \\
5&\underline{5}&&&&&&&& && 25 \text{ points} \\
\underline{5}&3&2&&&&&&& && 6 \\
\underline{4}&3&2&1&&&&&& && 4 \\
2&\underline{3}&2&1&2&&&&& && 4 \\
\underline{2}&2&2&1&2&1&&&& && 2 \\
1&\underline{2}&2&1&2&1&1&&& && 1 \\
1&1&\underline{2}&1&2&1&1&1&& && 1 \\
1&1&1&1&\underline{2}&1&1&1&1& && 1 \\
1&1&1&1&1&1&1&1&1&1 && 1 \\ \hline
\multicolumn{10}{r}{\textbf{Total Score}} & = & 45 \text{ points}
\end{array}
\]
%
On each line, the underlined stack is divided in the next step.

\bparts 

\ppart Can you find a better strategy?  Experiment with a few strategies,
and before looking at the next page, see if your team can guess what's
going on.

\examspace

\ppart As you may have guessed, the strategy is irrelevant: the score is
determined solely by the number of boxes.  Confirm this using strong
induction to prove that the predicate
\[
S(n) \eqdef \text{every way of unstacking $n+1$ blocks gives a score of
  $(n+1)n/2$}
\]
holds for all $n \in \naturals$.

\solution{
\begin{proof}
The proof is by strong induction.

\textbf{Base case:} If $n = 0$, then there is only one
block.  No moves are possible, and so the total score for the game is
$1(1 - 1)/2 = 0$.  Therefore, $S(0)$ is true.

\textbf{Inductive step:} Assume that $S(0), \dots, S(n)$ are all true for
some $n \in \naturals$.  We must show that $S(n+1)$ is true, namely, if we
start with a stack of $n+2$ blocks, the final score will be
\begin{equation}\label{finscore}
\frac{(n+2)(n+1)}{2}
\end{equation}

To prove this, suppose the first move splits this stack into substacks of
sizes $a$ and $b$ where $a+b = n+2$ and $0<a,b\leq n+1$.  Now the total
score for the game is the sum of points for this first move plus points
obtained by unstacking the two resulting substacks:
%
\begin{align*}
\text{total score}
    & = \text{(score for 1st move)} \\
    & \quad + \text{(score for unstacking $a$ blocks)} \\
    & \quad + \text{(score for unstacking $b$ blocks)} \\
    & = ab + \frac{a(a-1)}{2} + \frac{b(b-1)}{2} & \text{by $S(a)$ and $S(b)$}\\
    & = \frac{(a+b)^2-(a+b)}{2} = \frac{(a+b)((a+b)-1)}{2}\\
    & = \frac{(n+2)(n+1)}{2}
\end{align*}
which equals~\eqref{finscore} as claimed.  This completes the inductive step.

By strong induction, we conclude that $S(n)$ holds for all $n \in
\naturals$.
\end{proof}
}

\eparts
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem ends here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{latex-macros/handout-postamble.tex}