6.042/18.] Mathematics for Computer Science February 10, 2005 Srini devadas and Eric Lehman Lecture notes duction ii 1 Unstacking Here is another wildly fun 6.042 game that' s surely about to sweep the nation! 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 m 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 night proceed as follows Stack Heights 25 points 532 4321 23212 6442 22 1 222 121 111 111121111 1111111111 ats On each line, the underlined stack is divided in the next step. Can you find a better strategy? 1.1 Strong Induction Strong induction and ordinary induc ing a variant of induction called strong induction We'll analyze the unstacking game ion are used for exactly the same thing: proving that a predicate P(n)is true for all n E N6.042/18.062J Mathematics for Computer Science February 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Induction II 1 Unstacking Here is another wildly fun 6.042 game that’s surely about to sweep the nation! 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 follows: Stack Heights Score 10 5 5 25 points 5 3 2 6 4 3 2 1 4 2 3 2 1 2 4 2 2 2 1 2 1 2 1 2 2 1 2 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Total Score = 45 points On each line, the underlined stack is divided in the next step. Can you find a better strategy? 1.1 Strong Induction We’ll analyze the unstacking game using a variant of induction called strong induction. Strong induction and ordinary induction are used for exactly the same thing: proving that a predicate P(n) is true for all n ∈ N