Even is even and odd is...

It is old-fashioned, and made of wood rather than electrons, but nonetheless many of you will be familiar with the puzzle above. It consists of 15 numbered tiles placed in a 4x4 box, leaving one empty space in the bottom right corner. The challenge is to use the empty space to slide the tiles into numerical order.

This is the 15 Puzzle, and when it appeared about 1880 it created as big a craze as Rubik's Cube a hundred years later. The most popular version was due to the famous puzzler Sam Loyd, who presented all the tiles in order, except with the 14 and the 15 swapped. Loyd offered a prize of $1000 - worth about $20,000 today - to the first person to solve his puzzle. The prize was never collected. We'll explain why.

Imagine you were permitted to remove the tiles from their box. Then a methodical approach to "solving" the puzzle would be to successively swap pairs, until all tiles were in order.

In our example above, a specific strategy would be to start by swapping 1 and 14, ensuring 1 is in its correct place. Next, we swap 2 and 14, so that 2 is correct, and so on. Obviously this will "solve" the puzzle, and in fact after six swaps we'll be done. Of course there are many other swapping strategies one could devise.

Now here is a very curious fact: though there are many different swapping strategies, all of them will require an even number of swaps to solve our example above. Similarly, for a different starting arrangement our specific strategy may require an odd number of swaps, but then all strategies for that starting arrangement would require an odd number of swaps.

This is very interesting, but what does it have to do with winning Loyd's Prize? As we explain below, an initial arrangement can only be solved by sliding the tiles if a swapping strategy requires an even number of swaps. So, our pictured arrangement can indeed be solved by sliding. However, Loyd's arrangement can be solved with exactly one swap. So, as Sam Loyd undoubtedly knew, his puzzle is impossible to solve by sliding, and his money was always safe.

So why does swapping tell you whether the puzzle is solvable? Think of the empty space as a sixteenth tile. Then sliding a tile into the empty space is just the same as swapping with the blank tile. Now imagine that the wooden base underneath the tiles is shaded like a chessboard, with the bottom right square being white. Then a solution to Loyd's problem would consist of a sequence of swaps with the blank tile, and with the visible square underneath changing colours on every move: black, white, black, white ... Since we start and end with a white square visible in the bottom right corner, this means that any solution must consist of an even number of swaps.

The underlying "always even" and "always odd" rule for swapping holds true much more generally. For example, you might rearrange your dinner guests at the table by making five swaps, but you could not have produced that same new arrangement with an even number of swaps.

More fiendishly, you can apply the same principle to play a joke on that smug friend who brags about being able to solve Rubik's Cube: remove a little cube on the edge, give it a half-rotation and reinsert. The resulting Rubik's Cube is now impossible to solve. It should provide your Rubik Master with endless hours of "fun".

Burkard Polster teaches mathematics at Monash and is the university's resident mathemagician, mathematical juggler, origami expert, bubble-master, shoelace charmer, and Count von Count impersonator.

Marty Ross is a mathematical nomad, currently lecturing at the University of Melbourne. His hobby is smashing calculators with a hammer.

www.qedcat.com