Consider the problem of solving a jigsaw puzzle, in which pieces fit together to

Question

Consider the problem of solving a jigsaw puzzle, in which pieces fit together to form larger connected blocks. Define a move to be the process of connecting one block of any size 1 to another block of any size 1. Thus connecting one piece to another piece counts as a move, and connecting one block of size 25 to a second block of size 8 also counts as one move. Use strong induction to prove that no matter how a puzzle is constructed and how the moves are carried out, exactly n 1 moves are needed to solve a puzzle with n pieces.

Explanation / Answer

It takes n-1 moves to complete the n pieces puzzle to solve.

The base case is n= 1 . It is trival to say that number of moves is 0 .So it
holds for the base case.

We will assume it for n piece and prove it for n+1 pieces.

For n+1 pieces we will be needing n moves.

If we start our moves then by n-1 moves , n pieces have been fixed correctly. now
the (n+1)the piece can be fitted to the correct position.So it will be just
one move. This means that number of total moves will be n-1+1 and that is n.
Hence we have proved that n+1 pieces will take n moves.

So the theory has been proved.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.