Tuesday, March 15, 2011

Splitting Chocolate Bars

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?
Ans. N-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

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

No comments: