The Impossibility of the Game of 15

                                 state 1                                                                         state 2

The Game Of 15

The Object of the game of 15 is to get from state 1 to state 2 only with transpositions 1 involving 16 and its neighbors.

The Proof of Impossibility

The object can also be stated as

(14 15)=(an 16)(an-1 16)(an-2 16)…(a3 16)(a2 16)(a1 16)

We notice that the left side is only 1 transposition so the parity of the left side is -1.

We also notice that the number of ups the 16 has to move is equal to the number of downs and  the number of lefts is equal to the number of rights.Since each up,down,left, and right are transpositions there are an even number of transpositions. Then the parity of the right side is (-1)even=1. But that is a contradiction so therefore the game of 15 is impossible.

QED


1 :

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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