Fifteen
Task number: 2464
Find the criterion for the solvability of the so called “Fifteen”.
This is a puzzle where 15 square stones numbered from 1 to 15 are placed in a \(4\times 4\) grid, but instead of one stone there is a free space that allows to move stones. At the beginning, the stones are arbitrarily shuffled, the aim of the game is to arrange them from 1 to 15.
To begin, aim for a position where the stones are arranged so that the numbers 14 and 15 are interchanged as in the picture.
Hint
Consider the following order of the squares:
The given position then corresponds to the permutation: \((1{,}2,3{,}4,8{,}12,14{,}15,13{,}9,5{,}6,7{,}11,10)\). Try to derive some rule for such orders.
Resolution
Positions will be represented as numbers of the squares \(1{,}2,…,15\) ordered as they show up on the curve (any other connected curve would be good enough). This is a permutation of \(1,…,15\).
It suffices to argue that any move preserves the sign of the permutation, i.e. solvable ones have positive sign, while non-solvable negative. Any move shifts a stone between positions with odd and even index (on the curve), i.e. the number of stones that have been passed is always even.
Note: Samuel Lloyd (1841–1911), popularized this puzzle in 1878 by declaring that the premium $1.000 will be awarded to anyone, who first finds a sequence of moves that interchanges squares 14 and 15. We see that it is not possible, however, two trick “solutions” are shown in the following pictures.
First trick solution - different placement of empty slot:
Second trick solution - rotate the grid:
