In his last wager, the Baron challenged Sir R----- to put a four by four square of tiles, numbered from one to sixteen, into sequential order from top-left to bottom-right by rotating two by two squares of adjacent tiles. That Sir R----- should have had a prize of three coins if he had succeeded and the Baron should have had one of two coins if he had not suggests that the key to reckoning whether Sir R----- should have taken this wager is to figure whether or not every arrangement of the tiles might be arrived at through such manipulations.

That the square has rotational and reflectional symmetries means that a necessary and sufficient condition for this to be the case is that there exist tours of moves that begin with the tiles in order

and end with them having the exchanged pairs

since, by the aforementioned symmetries, these allow us to exchange any pair of adjacent tiles. Furthermore, if we can exchange tiles \(t_1\) and \(t_2\), and also tiles \(t_2\) and \(t_3\), then we can exchange tiles \(t_1\) and \(t_3\) with

Irritatingly, there is no tidy way to prove that these transformations are possible and so we must search for particular sequences of moves that result in them.

The trick is to consider a three by three version of the game

in which we can exchange the eighth and ninth tiles with

By reflectional symmetry we can trivially also exchange the seventh and eighth tiles and hence the first two transformations of the four by four case can be achieved through such moves upon the tiles in rows one to three and columns one to three.

Similarly, the last two of them may be arrived at by performing such transformations upon rows two to four.

Now this is a tremendously laborious scheme, but it nevertheless proves that every arrangement of the tiles may be arrived at, and consequently undone, with such moves and therefore Sir R----- should most certainly have profited from the wager and I should have had no compunction whatsoever in suggesting that he accepted it!

That the square has rotational and reflectional symmetries means that a necessary and sufficient condition for this to be the case is that there exist tours of moves that begin with the tiles in order

and end with them having the exchanged pairs

since, by the aforementioned symmetries, these allow us to exchange any pair of adjacent tiles. Furthermore, if we can exchange tiles \(t_1\) and \(t_2\), and also tiles \(t_2\) and \(t_3\), then we can exchange tiles \(t_1\) and \(t_3\) with

\[
t_1 t_2 t_3 \to t_2 t_1 t_3 \to t_2 t_3 t_1 \to t_3 t_2 t_1
\]

and so, with repeated applications of such adjacent exchanges, we can exchange any pair of tiles and may consequently put them all into any particular arrangement.Irritatingly, there is no tidy way to prove that these transformations are possible and so we must search for particular sequences of moves that result in them.

The trick is to consider a three by three version of the game

in which we can exchange the eighth and ninth tiles with

By reflectional symmetry we can trivially also exchange the seventh and eighth tiles and hence the first two transformations of the four by four case can be achieved through such moves upon the tiles in rows one to three and columns one to three.

Similarly, the last two of them may be arrived at by performing such transformations upon rows two to four.

Now this is a tremendously laborious scheme, but it nevertheless proves that every arrangement of the tiles may be arrived at, and consequently undone, with such moves and therefore Sir R----- should most certainly have profited from the wager and I should have had no compunction whatsoever in suggesting that he accepted it!

\(\Box\)

## Leave a comment