Problem 4. (15 points) The box stacking game is as follows: you start with a stack...

Transcribed Image Text:

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! 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!

Answer rating: 100% (QA)

Lets break down the problem step by step Base Case n1 When there is only one box the game ends immediately and you get 0 points Base Case n2 With two ... View the full answer