The Fifteen Puzzle

A friend introduced me today to this amusing problem and explained the solution to me. I had actually already read about it some years ago but at the time thought it was too complicated for me and did not try to solve it or to read a proof. It is quite simple if you know a little bit about the symmetric group.

Let us state the problem. Fifteen squares are placed in a frame whose sides are four squares in length. There is an empty square left. The squares are numbered from one to fifteen, and the original configuration is

The goal is to reach the final configuration

by sliding the squares inside the frame.

Now if you are used to thinking in term of permutations, you see that the initial configuration was obtained from the final configuration by exchanging fifteen with fourteen, or to put it differently by applying the transposition (14,15) to the initial configuration. More subtly, if we push a little square in the empty square, what we in fact do is exchange this square with the empty square.  If we mentally give the number sixteen to the empty square and if we exchange it with the square number n, we are applying the transposition (n,16). In this language, to solve the puzzle is to find a sequence of transpositions \tau_1,\dots,\tau_p of the form (n,16) with 1\le n \le 15 such that

\tau_p \circ \dots \circ \tau_1 \circ (14,15)=id.

It is now easy to see that such a solution does not exist. Let us prove this by contradiction. Since we have a product of p+1 transpositions that is equal to the identity, it is of signature 1 and therefore p+1 must be even i.e. p must be odd. But if the empty square (a.k.a. square sixteen) comes back to the bottom right-hand corner, it has been exchanged an even number of times and therefore p must be even. Contradiction.

I thought that this puzzle had been invented by Sam Loyd, who offered a thousand dollars to anyone who would solve it. I think I had read it in one of Martin Gardner’s book. But apparently this is false.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s