We are given a chocolate bar with k squares of chocolate Our

We are given a chocolate bar with k squares of chocolate. Our task is to divide it into k 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 2x2, i.e. it has 4 squares. The first split makes two pieces of 2 squares each. 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 k squares, we need at most k - 1 splits.

Solution

using induction method

case (1) k = 1: P(1) is true because there is only a single square of chocolate, and 1 ? 1 = 0 splits are required.

case (2) 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.