\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem 
Theory Pig is trying to pack his belongings for Thanksgiving vacation.
He has $X$ items, each of which has weight $1$.  He has found a way to 
pack these items in his suitcase, along with appropriate packing
material, such that the weight of the suitcase with items inside
will be $X \cdot \sqrt{X}$.  \\
Theory Pig is a little bit worried about carrying that much weight, so
he goes to his good friend Alex Duran.  Alex offers to provide him
with a ``versatile packing strategy'' (and a loan of appropriate 
suitcases) that trivially gets a result
as good as Theory Pig's and should be able to do much better.  In return,
Theory Pig has to help Alex come up with a question for the final exam.\\
Theory Pig accepts the deal, but after experimenting with Alex's packing
strategy, realizes that he can't do any better than he already has done.
Prove it.\\

Note to fellow TA's.  One of the following two explanations should accompany this.
The first one is more clear, but may give too much information.  The second one doesn't
give away too much but may be less clear.

First:

More formally:\\
Alex's strategy is the following:  Pack $N$ items, each of identical weight
$Y$ by:\\
1.  Picking a value $A$, $1 \leq A \leq N$.\\
2.  Breaking the items up into $A$ groups of $N/A$ items each.
3.  Optimally(via Alex's method) packing those subgroups, creating $N/A$ groups of weight $C$ each.\\
4.  Packing the subgroups into a suitcase weighing $(N/A) \cdot C \cdot \sqrt{(N/A)}$\\

Theory Pig simply packs his $X$ items into $X \cdot 1 \cdot \sqrt{X}$.

Obviously Alex can match Theory Pig(for $N = X$) by picking $A = X$, so that $C = 1$ and
$(N/A) \cdot C \cdot \sqrt{(N/A)}$ = $X \cdot 1 \cdot \sqrt{X}$\\

Prove, using strong induction on $N$, that given any set of $N$ items, each of weight
$Y$, that the best Alex's strategy can do is $N \cdot Y \cdot \sqrt{N}$.
(This implies that Alex's strategy doesn't help Theory Pig).\\

Second:

More formally:\\
Alex's strategy is the following:  For any $N$ items, each with identical 
weight
$Y$, Theory Pig can pack the $N$ items into a suitcase such that the
weight of the suitcase after packing will be $N \cdot Y \cdot \sqrt{N}$.
Each suitcase, after packing, can be treated as an item.  Theory Pig's
$X$ items can trivially be packed into weight $X \cdot 1 \cdot \sqrt{X} =
X \cdot \sqrt{X}$.  The algorithm also allows a recursive approach.
For instance, $4$ items of weight $1$ each could be packed in pairs
into two items(suitcases) of weight $2 \cdot \sqrt{2}$ each, and 
then those items could be packed into a suitcase of weight\\
$2 \cdot (2 \cdot \sqrt{2}) \cdot \sqrt{2} = 8 = 4 \cdot 1 \cdot \sqrt{4}$.

Prove, using strong induction on $N$, that given any set of $N$ items,
each of weight $Y$, they cannot be packed better than $N \cdot Y \cdot \sqrt{N}$.
(This implies that Alex's strategy doesn't help Theory Pig).\\

{\bf Solution:}\\
\begin{proof}
Proof by strong induction on $N$.\\

Induction Hypothesis: $\forall N \geq 1$ : $P(N)$: Optimal packing of
$N$ items of identical weight $Y$ is $N \cdot Y \cdot \sqrt{N}$.\\

Base Case: There is only one way to pack one item, and that is to 
put it in it's own suitcase, with weight $1 \cdot Y \cdot 1 = 1 \cdot Y \cdot 1$.\\

Inductive Step: Assume $\forall K (1 \leq K \leq N)$ : $P(K)$ in order
to prove $P(N+1)$.

Let $A$ be a divisor of $N+1$ representing the number of groups into
which I subdivide the $N+1$ items.  There are two cases:\\

Case 1:\\
$A = N+1$.  If I pack all $N+1$ items directly into one suitcase,
the weight is $(N + 1) \cdot Y \cdot \sqrt{(N+1)}$.  This is not better
than $(N + 1) \cdot Y \cdot \sqrt{(N+1)}$.  \\

Case 2:\\
$A < N+1$.  I pack $A$ sets of $\frac{N+1}{A}$ items, one set per
suitcase.  Each suitcase then weighs, (optimally, by the inductive
hypothesis) $\frac{N+1}{A} \cdot Y \cdot \sqrt{\frac{N+1}{A}}$, and I 
have $A$ such 
suitcases.  Packing these $A$ items optimally produces total weight\\
$A \cdot (\frac{N+1}{A} \cdot Y \cdot \sqrt{\frac{N+1}{A}}) \cdot \sqrt{A} = $\\
$(A \cdot \frac{N+1}{A}) \cdot Y \cdot (\sqrt{\frac{N+1}{A}} \cdot \sqrt{A}) = $\\
$(N + 1) \cdot Y \cdot \sqrt{(N+1)}$\\
Which is also not better than $(N + 1) \cdot Y \cdot \sqrt{(N+1)}$\\

Since these two cases represent the only ways to pack, and neither is
better than the inductive hypothesis suggests, $P(n+1)$ holds.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}

