A well known children's puzzle has 15 numberes pieces arranged inside a square as shown. A move is made by sliding a piece into the empty position. Consider the empty position as occupied by the number 16, so that every move is a transposition involving 16. Show that the order of the pieces can never be reversed. [Hint: show that if a product of transpoitions each involving the number 16 moves 16 to an even-numbered position on the 4X4 board then the number of transpostions must be even. Also consider the sign of the permutation which takes the "start" board to the "end?" board]
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
"start"
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1
"end?"