15Puzzle, sum of inversions - what's been summed?

Question

According to this page: http://mathworld.wolfram.com/15Puzzle.html it says that

While odd permutations of the puzzle are impossible to solve

I've red this article: http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics) and, if I understand the formula given in it, specifically: $\text{inv}(A) = \# \{(A(i),A(j)) \mid i < j \text{ and } A(i) > A(j)\}$ I don't understand how this is true, if, given this example:

4  0  2  3  | 4  1  2  3  | 4  1  2  3  | 0  1  2  3  |
5  1  6  7  | 5  0  6  7  | 0  5  6  7  | 4  5  6  7  |
8  9  10 11 | 8  9  10 11 | 8  9  10 11 | 8  9  10 11 |
12 13 14 15 | 12 13 14 15 | 12 13 14 15 | 12 13 14 15 |

1  0  2  3  | 0  1  2  3  |
4  5  6  7  | 4  5  6  7  |
8  9  10 11 | 8  9  10 11 |
12 13 14 15 | 12 13 14 15 |

inversion i = 1 > j = 0, A(i) = 0 < A(j) = 4
inversion i = 2 > j = 0, A(i) = 2 < A(j) = 4
inversion i = 3 > j = 0, A(i) = 3 < A(j) = 4
inversion i = 5 > j = 0, A(i) = 1 < A(j) = 4
inversion i = 5 > j = 2, A(i) = 1 < A(j) = 2
inversion i = 5 > j = 3, A(i) = 1 < A(j) = 3
inversion i = 5 > j = 4, A(i) = 1 < A(j) = 5

(4 0 2 3 5 1 6 7 8 9 10 11 12 13 14 15)
 |-| | | |-|
 |---| |   |
 |-----|   |
 |---------|
     |-----|
       |---|

There is the total of 7 inversion (obviously, odd, and should be unsolvable, but it is solved above in 6 steps). Where did I go wrong at counting inversions?

Answer 1

If you read the MathWorld article carefully, you’ll see that the actual statement is a little more complicated than the shorthand version that you quoted. If $N$ is the number of inversions in the initial permutation of the $15$ of the $15$ tiles, and $e$ is the row number of the initial location of the empty cell, a solution is possible if and only if $N+e$ is even.

However, this doesn’t resolve your question, because in your example $N=6$ and $e=1$, so $N+e=7$, which is odd.

The resolution lies in the definition of solvable: a position is solvable if you can reduce it to

$$\begin{array}{c} 1&2&3&4\\ 5&6&7&8\\ 9&10&11&12\\ 13&14&15&\square \end{array}$$

with the empty cell in the lower right. In fact that’s impossible with your configuration. If you made your final configuration the goal, your solvable positions would be exactly the ones that are unsolvable in the standard puzzle, and vice versa.

Answer 2

In the cited phrase about the 15 puzzle, it is assumed that the puzzle is handed to you with the empty square in the right lower place. It is this condition that ensures that the number of inversions has to be even because you can follow the movement of the empty square and see that you have to make an even number of moves.