The jigsaw puzzles are assmebled by fitting 2 pieces togethe

The jigsaw puzzles are assmebled by fitting 2 pieces together to form a small block, adding a single piece to a block to form a bigger block, or fitting 2 blocks together. Each of these moves is considered a step in the solution. Use induction to prove that the number of steps required to assemble an n-piece jigsaw puzzle is n 1

Solution

Basic case : consider that the puzzle has 1 piece then we know that 0 steps are required to put it together

Hence it is true for n=1 piece.

Induction hypothesis : we can say that any puzzle with l pieces, where l < k, can be put together in l 1 moves

consider a puzzle with k pieces.

we know that there are two possible last moves.

1) adding a piece to an k 1-piece puzzle,

2) putting together two smaller pieces of sizes m and l such that m + l = k

In the first case,

According to the inductive hypothesis we know that the k 1-piece puzzle required k 2 moves to assemble

The k-piece puzzle then requires (k 2) + 1 = k 1 moves that is k 2 for the k 1 pieces and one extra move for adding the last piece

In the 2nd case :

According to the inductive hypothesis tm pieces puzzle required m 1 moves and the l pieces puzzl erequired l 1 moves to put together

now to put the whole puzzle together we need (m 1) + (l 1) + 1 moves that is m 1 for the first part l 1 for the second part and 1 extra move for putting the two together

but we know that m + l = k so,

(m - 1) + (l - 1) + 1 = m + l - 1 = k - 1

so it takes k 1 moves to assemble the puzzle

Hence by induction we can say that n-piece puzzle requires n 1 moves to assemble.