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?"