Question: Assume you have a chocolate bar consisting, as usual, of a number of squares arranged in a rectangular pattern. Your task is to split the bar into small squares (always breaking along the lines between the squares) with a minimum number of breaks. How many will it take?

Answer:

As many as there are small squares minus 1.

The number of moves needed to break it into separate squares is invariant with regard to the actual sequence of moves.

Proof (by induction)
  1. If there are just two squares we clearly need just one break.
  2. Assume that for numbers 2<m<N we have already shown that it takes exactly m-1 breaks to split a bar consisting of m squares. Let there be a bar of N squares. Split it into two with m1 and m2 squares, respectively. Of course, m1 + m2 = N. By the induction hypothesis it will take (m1-1) breaks to split the first bar and (m2-1) to split the second one. The total will be 1 + (m1-1)+(m2-1) = N-1.

Proof #2
Let start counting how many pieces we have after a number of breaks. The important observation is that every time we break a piece the total number of pieces is increased by one. (For one bigger piece have been replaced with two smaller ones.) When there is no pieces to break, each piece is a small square. At the beginning (after 0 breaks) we had 1 piece. After 1 break we got 2 pieces. As I said earlier, increasing the number of breaks by one increases the number of pieces by 1. Therefore, the latter is always greater by one than the former.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.