Recitation 4 3 Problem: Breaking a chocolate bar We are given a chocolate bar with m x n squares of chocolate, and our task is to divide it into mn individual squares. We are only allowed to split one piece of chocolate at a time using a vertical or a horizontal break For example, suppose that the chocolate bar is 2 x 2. The first split makes two pieces both 2 x 1. Each of these pieces requires one more split to form single squares. This gives a total of three splits Use strong induction to conclude the following Theorem. To divide up a chocolate bar with m x n squares, we need at most mn-1 splits Solution. This theorem does not immediately lend itself to an induction proof, since there are two variables. In general, propositions involving several natural-valued vari ables can often be proved by using a sort of nested induction. However, in this case, we can get by with a single-variable induction and a trick Intuitively, to break up a big chocolate bar, we need one split to make two pieces, and then we can break up the two pieces recursively. This suggests a proof using strong in duction on the size of the chocolate bar, where size is measured in chocolate squares. Now instead of a problem involving two variables(the two dimensions), we have a problem in one variable(the size). With this simplification, we can prove the theorem using strong induction Proof. The proof is by strong induction on the size of the chocolate bar. Let P(k)be the proposition that a chocolate bar of size k requires at most k-1 splits Base case, k= 1: P(1)is true because there is only a single square of chocolate, and 1=0 splits are required Induction step: We suppose k> 1 and any chocolate bar of size s, where 1<s< k, requires at most s-1 splits. We must now show there is a way to split a chocolate bar of size k+ l with at most k splits To do this, first break the chocolate bar of size k+l into two smaller pieces of size p and q where p+q=k+1. This is certainly possible because the size of the bar is at least two Now the pieces of sizes p and g are between one and k, so by strong induction, breaking these two pieces into single squares requires only p-l and q-1 splits, respectiv total number of splits required to break the bar of size k l into single squares is therefore at most1+(P-1)+(q-1)=p+q-1=(k+1)-1 This shows that P()implies P(k+1), and the claim is proved by strong induction. ORecitation 4 4 3 Problem: Breaking a chocolate bar We are given a chocolate bar with m × n squares of chocolate, and our task is to divide it into mn individual squares. We are only allowed to split one piece of chocolate at a time using a vertical or a horizontal break. For example, suppose that the chocolate bar is 2 × 2. The first split makes two pieces, both 2 × 1. Each of these pieces requires one more split to form single squares. This gives a total of three splits. Use strong induction to conclude the following: Theorem. To divide up a chocolate bar with m × n squares, we need at most mn − 1 splits. Solution. This theorem does not immediately lend itself to an induction proof, since there are two variables. In general, propositions involving several natural­valued vari￾ables can often be proved by using a sort of nested induction. However, in this case, we can get by with a single­variable induction and a trick. Intuitively, to break up a big chocolate bar, we need one split to make two pieces, and then we can break up the two pieces recursively. This suggests a proof using strong in￾duction on the size of the chocolate bar, where size is measured in chocolate squares. Now instead of a problem involving two variables (the two dimensions), we have a problem in one variable (the size). With this simplification, we can prove the theorem using strong induction. Proof. The proof is by strong induction on the size of the chocolate bar. Let P(k) be the proposition that a chocolate bar of size k requires at most k − 1 splits. Base case, k = 1: P(1) is true because there is only a single square of chocolate, and 1 − 1 = 0 splits are required. Induction step: We suppose k ≥ 1 and any chocolate bar of size s, where 1 ≤ s ≤ k, requires at most s − 1 splits. We must now show there is a way to split a chocolate bar of size k + 1 with at most k splits. To do this, first break the chocolate bar of size k+1 into two smaller pieces of size p and q where p + q = k + 1. This is certainly possible because the size of the bar is at least two. Now the pieces of sizes p and q are between one and k, so by strong induction, breaking these two pieces into single squares requires only p − 1 and q − 1 splits, respectively. The total number of splits required to break the bar of size k+1 into single squares is therefore at most 1 + (p − 1) + (q − 1) = p + q − 1 = (k + 1) − 1 = k. This shows that P(k) implies P(k+1), and the claim is proved by strong induction