Problem Set 2 at a time. This gives a score of: n+(n-1)+…+3+2≈m(m+1)∠1 (n+2)(7-1) Now we must prove that there is no better strategy Proof. We use strong induction. Let P(n)be the proposition that unstacking n bricks is th at most(n +2)(n-1)/2 points Base case: P(1)is true because the game ends immediately when there is only 1 brick Thus, the players score is 0, which is the value of (n+2)(n-1)/2 when n= 1 Inductive step: Now assume that P(1),., P(n-1)are all true in order to prove P(n), where n> 2. Suppose the stack of n bricks is split into stacks of height c and n-1, where 0<a<n. The player's best possible score for the game is then (n-x)+x)+(x+2)(x-1)/2+(n-x+2)(n-x-1)/2 for first move to unstack e bricks to unstack n- bricks Here we are using the assumptions P(a)and P(n-a), which specify the best possible scores for unstacking c and n-a bricks. Now we must choose a to maximize this expres- sion. The derivative with respect to is 2.c-n. Thus, the expression decreases as c grows from 1 to n/2 and then increases symmetrically as grows from n/2 to n-1. Therefore, the maximum is achieved when z =1 or a=n-1. In both cases, the expression above is equal to (n+2)(n-1) o we have shown that P(1),., P(n-1)imply P(n) Therefore, P(n)is true for all n 2 l by the strong induction principleProblem Set 2 7 at a time. This gives a score of: n(n + 1) n + (n − 1) + . . . + 3 + 2 = − 1 2 (n + 2)(n − 1) = 2 Now we must prove that there is no better strategy. Proof. We use strong induction. Let P(n) be the proposition that unstacking n bricks is worth at most (n + 2)(n − 1)/2 points. Base case: P(1) is true because the game ends immediately when there is only 1 brick. Thus, the player’s score is 0, which is the value of (n + 2)(n − 1)/2 when n = 1. Inductive step: Now assume that P(1), . . . , P(n − 1) are all true in order to prove P(n), where n ≥ 2. Suppose the stack of n bricks is split into stacks of height x and n−x, where 0 < x < n. The player’s best possible score for the game is then: ((n − x) + x) + (x + 2)(x − 1)/2 + (n − x + 2)(n − x − 1)/2 � �� � � �� � � �� � for first move to unstack x bricks to unstack n − x bricks Here we are using the assumptions P(x) and P(n − x), which specify the best possible scores for unstacking x and n−x bricks. Now we must choose x to maximize this expres￾sion. The derivative with respect to x is 2x−n. Thus, the expression decreases as x grows from 1 to n/2 and then increases symmetrically as x grows from n/2 to n − 1. Therefore, the maximum is achieved when x = 1 or x = n − 1. In both cases, the expression above is equal to: (n + 2)(n − 1) 2 So we have shown that P(1), . . . , P(n − 1) imply P(n). Therefore, P(n) is true for all n ≥ 1 by the strong induction principle