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

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?

-

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.

-
Oh, I see now, thank you! –  wvxvw May 18 '12 at 9:55