Question

rove that a rectangular chocolate bar with n squares takes n-1 "breaks" to break it into individual uares.

Answer 1

We prove that a rectangular bar with n squares always requires n−1 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 m−1 breaks. We show that a bar with n squares requires n−1 breaks.

Break the n-bar into two 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 a−1breaks, and the b-rectangle will use b−1breaks, for a total of 1+(a−1)+(b−1)=n−1.

It is clear that

For n=1, we need 0 break. For n=2, we need 1 break. For n=3, we need 2 breaks. So say for n=j, its true and we need j-1 breaks and its true for all j>0&& j<=k. So a bar of k+1 squares can be broken down to 2 rectangles with squares < k , which is already true. Hence proved.