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:
Post a Comment