Question

A jigsaw puzzle is put together by successively joining pieces that fit together into blocks. A move is made each time a piece is added to a block, or when two blocks are joined. Use strong induction to prove that no matter how the moves are carries out, exactlyn -1 moves are required to assemble a puzzle with n pieces.

Short answer

It has been proved that it takes exactly n - 1 moves are required to assemble a puzzle withn pieces.

Step-by-step solution

Describe the given information

Given a jigsaw puzzle is put together by successively joining pieces that fit together into blocks. A move is made each time a piece is added to a block, or when two blocks are joined.

Prove using strong induction

Let$P\left(n\right)$ : It takes exactlyn - 1 moves are required to assemble a puzzle with n pieces.

The basis step:$P\left(1\right)$ is trivially true.

Inductive hypothesis:$P\left(j\right)$ is true for all $j<n$, and consider a puzzle with n pieces.

To show: The statement$P(k+1)$ is true.

Proof:The final move must be the joining of two blocks, of size kand $n-k$for some integer k,$1\le k\le n-1$.

Inductive hypothesis: It required $k-1$moves to construct the one block, and $n-k-1$moves to construct the other.

Therefore $1+(k-1)+(n-k-1)$ moves are required in all, so$P\left(n\right)$is true.

Notice that for variety here we proved $P\left(n\right)$ under the assumption that P(j) was true forj <n;so nplayed the role that k+1plays in the statement of strong induction.