Solution

A jigsaw puzzle is solved by putting its pieces together in the correct way. Show that exactly $n-1$ moves are required to solve a jigsaw puzzle with $n$ pieces, where a move consists of putting together two blocks of pieces, with a block consisting of one or more assembled pieces.


We shall argue using the second principle of mathematical induction (i.e., the strong principle of mathematical induction)...

First, we establish the basis step. Consider a puzzle that consists of only $1$ piece. Such a puzzle is already "solved", so zero moves are required. As $n-1=0$, the basis step is established.

Now we turn our attention to the inductive step. Using strong induction, we need to show that if the statement holds whenever $n \le k$, then it must also hold when $n=k+1$.

Consider the last move that solves a puzzle of $k+1$ pieces. Suppose that, during this last move the blocks joined were named $A$ and $B$, and had $a$ and $b$ pieces respectively. Note, $a+b = k+1$ and $a,b \le k$. As such by the inductive hypothesis, block $A$ could be put together in $a-1$ moves and block $B$ could be put together in $b-1$ moves. Thus, the entire puzzle can be put together in $(a-1) + (b-1) + 1 = a + b - 1 = k$ moves -- which is what we needed to show.

Hence, by the strong principle of mathematical induction, exactly $n-1$ moves are required to solve a jigsaw puzzle with $n$ pieces.

QED.