state 1 state 2
The Game Of 15
The Object of the game of 15 is to get from state 1 to state 2 only with transpositions 1 involving 16 and its neighbors.
The Proof of Impossibility
The object can also be stated as
(14 15)=(an 16)(an-1 16)(an-2 16)…(a3 16)(a2 16)(a1 16)
We notice that the left side is only 1 transposition so the parity of the left side is -1.
We also notice that the number of ups the 16 has to move is equal to the number of downs and the number of lefts is equal to the number of rights.Since each up,down,left, and right are transpositions there are an even number of transpositions. Then the parity of the right side is (-1)even=1. But that is a contradiction so therefore the game of 15 is impossible.