15 Puzzle

On the picture you can see the famous "15 Puzzle". The rules are simple - you can slide any of the 15 squares to the empty spot, if it neighbors with it. The question is: if the squares with numbers 14 and 15 are exchanged, can you solve the puzzle, i.e. can you bring it to the state shown on the picture?



No, you can't. In order to see this, at each moment count the number of pairs of little squares, which are wrongly ordered. For example if the numbers on the first row are 7, 2, 12 and 5 in this order, then 7 and 2, 7 and 5, and 12 and 5 are wrongly ordered. Notice that after every move you make, the number of wrongly ordered pairs changes with odd number - +/-3 or +/-1. If you want to go from the state in which squares 14 and 15 are exchanged to the solved state on the picture, you must make even number of moves and therefore you would change the number wrongly ordered pairs by an even number. However, the number of wrongly ordered squares in the starting state is 1, whereas in the ending state is 0, which yields a contradiction.