Stacking Game

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 shown in Figure;

On each line,

the underlined stack is divided in the next step.

Can you find a better strategy?

n 1 n 2Stack Heights Score 25 points N - - IN NIW W W IU INNNNNN 1 2 1 - N . 2 - 1 21 1 1 1 21 1 1 1 - - 1 1 1 1 1 1 Total Score = 45 points