Assume that a chocolate bar cconsists of n squares arranged

Assume that a chocolate bar cconsists 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 separtating 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

Answer:

We claim that the number of needed breaks is n-1.

We shall prove this for all positive integers n using strong induction.

The basis step: for n = 1 the basis step is clear.

In that case we don\'t need to break the chocolate at all, we can just eat it.

Suppose now that n > 2 and assume the assertion is true for all rectangular chocolate bars with fewer than n

squares. Then we break the chocolate into two pieces of size m and n - m where 1 < m < n .

By the induction hypotheses, the bar with m pieces requires m - 1 breaks

and the bar with n - m squares requires n - m - 1 breaks. Thus the original cholocate bar requires

1 + ( m -1 ) + ( n - m -1 ) breaks. This number equals n - 1 as required.