Problem 4. (15 points) The box stacking game is as follows: you start with a stack of n boxes. Then you make a sequence of moves; in one move you pick one stack and divide it into two smaller non-empty stacks. The game ends when you have n stacks, each containing one box. When you divide a stack into two stacks of sizes a and b, you get ab points. Your overall score is the sum of points you accumulate per move, from the starting position to when the game ends. What strategy should you follow to maximize your score? Hint: Play the game with 4 boxes-separate it into two stacks of 2 and 2 or into two stacks of 1 and 3. In both cases how many points do you collect on completion? Hmm, what if we started with 5 boxes instead? There are more ways to proceed - do different plays result in different final scores? Next, define the potential p (S) of a stack S with k boxes to be *(-), and the potential of a set of stacks 2 as the sum of the potentials of all its stacks. After each move, the potential decreases but you collect points. Add up the potential of the two stacks and the points earned. How does that compare to the original potential? Now use induction, and think chocolate bars!