Problem set 2 Next, we must show that P(k) implies P(k+ 1) for all k > 1. So assume that P(k) is true, and let r1,..., Ck+1 be a collection of positive integers with sum n. Then we can reason as follows: <3 The first step uses the assumption P(k), the second uses the preceding problem part, and the last step is algebra. This shows that P(k+ 1)is true, and so the claim holds by induction Problem 6. Suppose that you take a piece of paper and draw n straight lines, no one exactly on top of another, that completely cross the paper. This divides the paper into polygonal regions. Prove by induction that you can color each region either red or blue so that two regions that share a boundary are always colored differently.(Regions that share only a boundary point may have the same color. Solution. The proof is by induction. Let P(n) be the proposition that the regions defined by n lines can be colored red or blue so that adjacent regions are different colors Base case: If n =0, then there are no lines and the whole paper is a single region. Color it red. Adjacent regions are different colors trivially since there are no adjacent regions Thus, P(O)is true. Inductive step: Assume that P(n) is true. We prove that P(n 1) is also true. Given a configuration of n+1 lines, remove an arbitrary line l. by the assumption P(n), the plygonal regions defined by the remaining n lines can be colored red or blue so that adjacent regions are colored differently. Now add back the line l and invert the color of every region to one side of l. Adjacent regions on the same side of the line are different colors by the induction assumption P(n). Adjacent region on opposite sides of the line are different colors because the colors on one side were inverted. Therefore, P(n)implies P(n+1), and so P(n)is true for all n >0 by induction Problem 7. Let's consider a variation of the Unstacking game demonstrated in lecture. As before, the player is presented with a stack of n> 1 bricks. Through a sequence of moves, she must reduce this to n single-brick stacks while scoring as many points as possible. A move consists of dividing a single stack of (a+b) bricks(where a, b>0)into two stacks with heights a and b. Suppose that this move is worth a+ b points. Find the best strategy and use induction to prove that there is no better strategy Solution. Some experimentation suggests that the best strategy is to remove one block6 Problem Set 2 Next, we must show that P(k) implies P(k + 1) for all k ≥ 1. So assume that P(k) is true, and let x1, . . . , xk+1 be a collection of positive integers with sum n. Then we can reason as follows: x1 x2 · · · xk · xk+1 ≤ 3(n−xk+1)/3 · · xk+1 ≤ 3(n−xk+1)/3 3xk+1/3 · = 3n/3 The first step uses the assumption P(k), the second uses the preceding problem part, and the last step is algebra. This shows that P(k + 1) is true, and so the claim holds by induction. Problem 6. Suppose that you take a piece of paper and draw n straight lines, no one exactly on top of another, that completely cross the paper. This divides the paper into polygonal regions. Prove by induction that you can color each region either red or blue so that two regions that share a boundary are always colored differently. (Regions that share only a boundary point may have the same color.) Solution. The proof is by induction. Let P(n) be the proposition that the regions defined by n lines can be colored red or blue so that adjacent regions are different colors. Base case: If n = 0, then there are no lines and the whole paper is a single region. Color it red. Adjacent regions are different colors trivially since there are no adjacent regions. Thus, P(0) is true. Inductive step: Assume that P(n) is true. We prove that P(n + 1) is also true. Given a configuration of n + 1 lines, remove an arbitrary line l. By the assumption P(n), the polygonal regions defined by the remaining n lines can be colored red or blue so that adjacent regions are colored differently. Now add back the line l and invert the color of every region to one side of l. Adjacent regions on the same side of the line are different colors by the induction assumption P(n). Adjacent region on opposite sides of the line are different colors because the colors on one side were inverted. Therefore, P(n) implies P(n + 1), and so P(n) is true for all n ≥ 0 by induction. Problem 7. Let’s consider a variation of the Unstacking game demonstrated in lecture. As before, the player is presented with a stack of n ≥ 1 bricks. Through a sequence of moves, she must reduce this to n single­brick stacks while scoring as many points as possible. A move consists of dividing a single stack of (a + b) bricks (where a, b > 0) into two stacks with heights a and b. Suppose that this move is worth a + b points. Find the best strategy and use induction to prove that there is no better strategy. Solution. Some experimentation suggests that the best strategy is to remove one block