Problem 1. 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 · \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 ≤ A ≤ 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) · C · \sqrt{(N/A)}

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

Obviously Alex can match Theory Pig(for N = X) by picking A = X, so that C = 1 and (N/A) · C · \sqrt{(N/A)} = X · 1 · \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 · Y · \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 · Y · \sqrt{N}. Each suitcase, after packing, can be treated as an item. Theory Pig’s X items can trivially be packed into weight X · 1 · \sqrt{X} = X · \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 · \sqrt{2} each, and then those items could be packed into a suitcase of weight 2 · (2 · \sqrt{2}) · \sqrt{2} = 8 = 4 · 1 · \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 · Y · \sqrt{N}. (This implies that Alex’s strategy doesn’t help Theory Pig).

Solution:

Proof. Proof by strong induction on N.

Induction Hypothesis: ∀N ≥ 1 : P (N): Optimal packing of N items of identical weight Y is N · Y · \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 · Y · 1 = 1 · Y · 1.

Inductive Step: Assume ∀K(1 ≤ K ≤ 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) · Y · \sqrt{(N + 1)}. This is not better than (N + 1) · Y · \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} ·Y ·\sqrt{\frac{N+1}{A}}, and I have A such suitcases. Packing these A items optimally produces total weight A · (\frac{N+1}{A} · Y · \sqrt{\frac{N+1}{A}}) · \sqrt{A} =

(A · \frac{N+1}{A}) · Y · (\sqrt{\frac{N+1}{A}} · \sqrt{A}) =

(N + 1) · Y · \sqrt{(N + 1)}

Which is also not better than (N + 1) · Y · \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.