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.

say there is an image made into a slide puzzle in a grid of sections 4 wide and 6 high, the missing piece that is missing so you can slide the other pieces of the puzzle around is always the bottom right piece of the grid if the picture matches the complete puzzle, so, if all the pieces of the image even the missing one were randomly placed on the grid, is there ANY chance that the puzzle would be impossible to complete?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

It's entirely analogous to the 15-puzzle.

To show that not all initial positions allow you to get to the desired final position, note the following invariant.

Assume that in the final position you have the numbers from 1 to 23 written on the pieces starting in the top left corner, and proceeding row-wise to the bottom right corner, where you put 24 to represent the missing piece. Associate to this the identity permutation, obtained by reading the images of the numbers $1, \dots, 24$ row-wise from top left to bottom right.

When you exchange 24 with another piece, you are composing the given permutation with a $2$-cycle, thereby changing the parity. But you are also changing the block distance of 24 from the bottom right corner by 1, so $$ P = \text{parity of the permutation} + \text{parity of the block distance} $$ is preserved.

Now the final position has $P$ even. If you start with the initial position in which 22 and 23 are exchanged, $P$ for this position is odd, so you will never be able to get to the final position from here.

share|improve this answer
    
is there an equation to seperate the solvable configurations from the impossible configurations? –  JRowan Feb 27 '13 at 15:03
    
As @ChrisTaylor said in his answer, you can solve exactly those (half of the total number of) configurations for which $P$ is even. This is a bit more complicated to show. –  Andreas Caranti Feb 27 '13 at 15:06
    
thanks for your time, is it half of the P even and half of P odd are the solvable ones and vice versa for impossible? or either even or odd are solvable? im just trying to get it through my head. –  JRowan Feb 27 '13 at 15:13
    
Even P = solvable, odd P = unsolvable. (PS You're welcome!) –  Andreas Caranti Feb 27 '13 at 15:16
1  
im so happy right now, thank you, you live and you learn, notch on the belt –  JRowan Feb 27 '13 at 16:47
show 3 more comments

Yes. Exactly half of all random starting positions are solvable, and the other half are unsolvable.

share|improve this answer
add comment

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.