Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

No sooner was I done finishing a puzzle that I began to wonder the odds of a n-piece puzzle being solved on the first try by a spider-like mechanical assembler with n arms, each able to simultaneously place down one piece.

  1. All puzzle pieces have the same number of sides d.
  2. The number of possible orientations is constant amongst all pieces.
  3. In order to be 'solved', the pieces have to be in the correct order and in the correct orientation.

The probability that all pieces are in the correct order, I suppose, would be: $$ \frac{1}{n!} $$

The second component would be the odds that all the pieces are in the correct order. The odd of any one piece being in the correct orientation, I think, would be: $$ \frac{1}{d} $$

This is because a d-sided piece can be oriented in d different ways, assuming that all pieces have the same amount of possible orientations. (I get a gut feeling this is true, but cannot prove it.) Since there are n pieces, the odds of all pieces being oriented correctly would be: $$\frac{1}{d^n}$$

Combining both probabilities yields us the final odds: $$ \frac{1}{d^nn!} $$

Is this reasoning sound?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The reasoning is sound - apart from a possible small factor of four to account for "accidentally" solving the puzzle e.g. rotated by 90 degrees.

That's why I always say that correctly placing a single piece correctly reduces the problem typically by a factor of 1000 or more. However, you won't really notice that progress until only few pieces are left. As a matter of fact, human pattern matching capabilities make it appear that the beginning (typically completing the edges and some easily recognizeable areas of the puzzle) is easier than the laborious middle phase.

share|improve this answer
    
Wouldn't the accidental solutions account for a factor of d? One of my assumptions was that a d-sided piece could be oriented d ways. Thus, it would be 1/d^(n-1)n! –  ohBoy Nov 14 '12 at 17:48
    
Yes, $d$ not 4 - I was thinkingtoo conventionally. Then again, wrong orientation may well be considered not solving. –  Hagen von Eitzen Nov 14 '12 at 17:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.