## Picking pieces of a jigsaw puzzle

Here’s a pretty cool brainteaser suggested by Pierre Dangauthier in a comment on a previous post of mine.

In a bag, there are all the pieces of a complete squared jigsaw puzzle of size $N \times N$. You are just allowed to pick $Q$ pieces, one at a time, without replacements. After having seen the $Q$ pieces, what is your estimate of $N$? With which confidence?

I don’t know the name of this problem. If you do know, please let me know.

Tags:

### One Response to “Picking pieces of a jigsaw puzzle”

1. Glen Says:

Closely related to the classic capture-recapture problem, but with 3 categories and a special structure. Very interesting.

You go to a lake and catch and tag $r$ fish out of an unknown population. Let’s assume the fish “mix” randomly after sufficient time (for many kinds of fish this isn’t a good assumption, but bear with me). You catch $m$ fish, and $p$ of them are tagged. How many fish are in the lake?

Or, abstracting a bit – we have a total of $N$ objects, $r$ red ($r$ is known) and $N-r$ white. We sample $m$ objects and observe $p$ red and $m-p$ white. This is an inference problem involving the hypergeometric.

i) Imagine a simpler version of the jigsaw problem where edge pieces and internal pieces were indistinguishable. Essentially we’ve tagged 4 pieces in the capture-recapture problem.

ii) Imagine a slightly less simplified version of the jigsaw problem where now corners and edge pieces are indistinguishable (the pieces that go in the corners have been made to only have one straight side, so one “outside” edge of a corner has either a bump or notch, making it look like an edge piece).

In that case, there are $4N-4$ “edge” bits and $M=N^2 - 4 N + 4$ internal pieces. This is a bit like capture-recapture but with a very special structure. I think this simpler problem captures many of the difficulties of the original jigsaw problem.

(The full problem involves inference about the population size in a multivariate hypergeometric but with a special structure.)

Thanks for the puzzle! It bears thinking about.