Consider jigsaw puzzle P. If its pieces are identically-shaped, is the difficulty of the puzzle greater or smaller than with a puzzle where pieces can only be fit into some of the others?

*Claim.* Differently-shaped pieces make a puzzle easier to solve.

*Proof.*

Consider a box P, where every piece p_{i} has an exact match with either two (for corner pieces), three (edge pieces), or four (internal pieces) other pieces P_{match,i} = {p_{m}} (so 2 ≤ |P_{match,i}| ≤ 4). Consider also those pieces P_{imp,i} = {p_{j}}, for which an imperfect match exists with p_{i}. There is a tolerance t_{i} ∈ T associated with each p_{i}, where t_{i} > z for some lower bound z. This tolerance expresses the probability of a piece matching any other piece, and is a function of the shape of its teeth and concavities.

The tolerance for any p_{i} in a puzzle with identically-shaped pieces is the limit as t_{i} → 1, since any piece can fit into any other piece. The size of the set of pieces with which p_{i} fits (|P_{fit,i}| = |P_{match,i}| + |P_{imp,i}|) is directly proportional to the tolerance for that piece, or |P_{fit,i}| = x|1 - t_{i}|, for some x ∈ ℜ: the lower the tolerance, the less likely p_{i} is to fit with any p_{j}, and thus there are fewer pieces with which it can have an imperfect fit. Note that P_{imp,i} varies with t_{i}, but P_{match,i} does not. Thus, as t_{i} → 0, |P_{imp,i}| → 0. If |P_{imp,i}| = 0, then the only p_{m} which fit p_{i} are the 2-4 pieces which are the correct neighbors.

Thus, the more similarly-shaped the pieces of a puzzle are, the more possible matches there are for any given piece, and the harder it is to find its correct neighboring pieces. QED.

Now, you may have noticed that this is not the most elegant proof out there. So I challenge you to write me a proof worth of the Book.

*1/15/08*: We have a winner! DTal, as you can see, has responded. Of course, there's still space for a runner-up if you can write a better mathematical proof than mine.