brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
|
UPDATE (1 October): No correct solutions have been submitted so
far to this riddle. The riddle will therefore run one extra month. However, this
time credit will be given both to solvers of the original question and to
solvers of the following simplified riddle: "using the optimal strategy,
what is the complexity of the smallest expected number of comparisons needed to
solve a shape-sorting puzzle with n shapes (rather than a jigsaw puzzle
with n tiles)?" A shape-sorting puzzle is a
children's toy where holes of various shapes need to be matched by pegs of
matching shapes. A comparison is made when a particular peg's shape is
compared against a particular hole's shape.
This riddle, in both its original and simplified form, will continue to run in parallel with a new October riddle. This riddle continues on the theme of jigsaw puzzles from the October 2007 and July 2014 riddles. The set-up of what a jigsaw puzzle is and what solving it means has been described in these two previous riddles (more succinctly in the July 2014 riddle) and will not be repeated here. Briefly, the earlier riddle asks about how difficult it is, in the worst case, to solve a puzzle when its degree is assumed to be bounded. The latter does the same without the degree bound. This month, we return to the world of jigsaw puzzles and ask how difficult it is to solve them in the average case when their degree is assumed to be bounded. Specifically, you are asked to give tight upper and lower bounds for the average-case solution complexity of any family of bounded degree puzzles. For completeness: the average-case solution complexity is the complexity, as a function of the number of tiles, of the expected number of tile match attempts one requires in order to determine unambiguously which tiles map to which positions. You are to assume that the optimal strategy is used (i.e., the strategy that minimises this expected value) and that the actual mapping is a random variable uniformly distributed between all n! possible mappings. As usual: prove your answer. |
List of solvers: |
Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!