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

Base Case: (n=1)

Since the size is 1X1 square, hence we require zero breaks to break the chocoloate

Hence the number of steps required is equal to 0

RHS = 1 -1 = 0

Induction Step: Let us assume that for less than n requires (n-1) steps

Hypothesis step: proof for n

Let us break the chocoloate into two pieces of size m and (n-m)

Number of steps for size m = (m-1)

Number of steps for sinze (n-m) = (n-m-1)

Hence the steps required to break size of n is equal to 1 + (m-1) + (n-m-1) = n-1 steps