## 15 puzzle

Probably you have seen before a 15 puzzle.

It is a set of 15 small squares inside a 4 times bigger square, numbered from 1 to 15. Therefore, one small square is left free. The idea is to reach the ordered position like in the picture after you scrambled the puzzle in some arbitrary way, leaving the down right corner empty.

The problem is to find all permutation of the small squares such that the desired solution state can be achieved in a finite number of moves without taking the small pieces out from the plane of the big square.

As an application, prove that if you swap any two of the pieces, the resulting puzzle cannot be solved.

**Solution:** Paint the small squares in two colors like a chessboard, and label the free cell as 16. A legal position is a position with 16 in the bottom right corner from which the initial state can be obtained by using transpositions of 16 with the adjacent cells. After one move, 16 is in a red cell. After 2 moves 16 is in a white cell. Continuing like this we see that if 16 starts from the bottom right corner and ends there, then there will be an even number of transpositions, and therefore the initial permutation must be even. This shows why if we swap two of the pieces we can never solve the puzzle. When 16 will be in the bottom right corner the resulting permutation will always be odd, and the identity is even.

Now to prove that all even permutation of the squares 1 to 15 provide a legal position, it’s enough to prove that every three cycle is legal. We know that 3-cycles of the form with fixed and variable generate all the even permutations. Using the bottom right 2×2 square we can see that the 3-cycle (11,12,15) is ok. Now it is easy to prove that if 11 goes to 12th place and 12 goes to 16th place then using cyclic moves we can swap any piece with 15, yielding cycles of the form (11,12,k). The proof is done. (of course, the details should be studied in detail)

Here you can find examples of impossible 15 puzzle positions. Try to prove that any such position can be transformed in the 14-15 swap position, which is obviously impossible. Good luck!