Assume that a chocolate bar consists of n squares arranged i

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 successively make to break the bar
into n separate squares. Use strong induction to prove
your answer

Solution

We prove that a rectangular bar with n squares always requires n1 breaks.

Recall that a \"break\" divides a rectangle into two rectangles along score lines.

For the induction step,

suppose that for all m < n, a bar with m squares requires m1 breaks.

We show that a bar with nn squares requires n1 breaks.

Break the n-bar into 2 rectangles, say of size a and b,

where a+b=n and a < n , b < n.

The breaking used 1 break.

By the induction assumption, dissecting the a-rectangle into unit squares will use a1 breaks, and the

b-rectangle will use b1 breaks, for a total of 1+(a1)+(b1) = n1