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 
. You are just allowed to pick 
pieces, one at a time, without replacements. After having seen the pieces, what is your estimate of 
? With which confidence?
I don’t know the name of this problem. If you do know, please let me know.
Like this:
Like Loading...
Tags: Puzzles
This entry was posted on October 22, 2007 at 14:42 and is filed under Puzzles. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
October 23, 2007 at 03:26 |
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
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 
fish, and 
of them are tagged. How many fish are in the lake?
Or, abstracting a bit – we have a total of
objects, 
red (
is known) and 
white. We sample 
objects and observe 
red and 
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
“edge” bits and 
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.