Question

Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, a smaller rectangular piece of the bar, can be broken along a vertical or a horizontal line separating the squares. Assuming that only one piece can be broken at a time, determine how many breaks you must successfully make to break the bar into n separate squares. Use strong induction to prove your answer

Short answer

It takes exactlyn -1 breaks to separate a bar.

Step-by-step solution

Describe given information

Given thata chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, a smaller rectangular piece of the bar, can be broken along a vertical or a horizontal line separating the squares.

Proof using strong induction

Claim: It takes exactly$n-i$ breaks to separate a bar. (or any connected piece of bar obtained by horizontal or vertical breaks.)

Let P(n) It takes$n-1$ breaks to separate a bar.

The basis step: The statement is true for n=1 (one piece and 0 breaks)

Inductive hypothesis: The statement is true for breaking into k or fewer pieces.

To show: The statement$P\left(k+1\right)$ is true.

Proof: The process must start with a break, leaving two smaller pieces. Rest of the process as breaking one of these pieces into and breaking the other piece into pieces, for somei between 0 and (inclusive of both). By inductive hypothesis it will take exactly i breaks to handle the first piece and$k-i$ breaks to handle the second piece. Therefore the total number of breaks will be$1+i+(k-i-1)=k$, as desired.