15 Puzzle question - trying to understand the proof

Question

I have been struggling to understand the proof proposed here to the 15 puzzle question (exercise 6) from the MIT Mathematics for computer science course.

The proof argues:

If a column move happens, the parity of the number of inversions is flipped (+3 or -3). Also, the parity of the row number of the blank square is flipped (+1 or -1). Given the start state with odd number of inversions and even row number for the blank square, the parity of those two variables will continue to differ after flipping them both to the opposite side.

But I have found a column movement that increases the amount of inversions by 2 and not 3.

Initial state => 1 inversions
A   B   C   D
E   F   G   H
I   J   K   L
M   O   N   

Second state => 1 + 3 = 4 inversions
A   B   C   D
E   F   G   H
I   J   K   
M   O   N   L

Third state (K moves left, N moves up) => 1 + 3 - 1 + 2 = 5 inversions
A   B   C   D
E   F   G   H
I   J   N   K
M   O       L

Can anybody explain why my counter example does not work or whether that proof is incorrect/incomplete?

I am sorry for posting a new question, but I am totally new to Stack Exchange and they won't let me comment in the original question until I have 50 reputation.

Answer 1

First: in your example you make two column moves, not one. That is, compared to your starting position, you have L going down, and N going up. But the post you refer to is talking about a single column move, not two. So, what you do is not a counterexample.

That said, there actually is something wrong with the post you refer to:

If a column move happens, the parity of the number of inversions is flipped (+3 or -3).

Here, the author seems to be thinking: "If I move a tile down, then afterwards it will now be behind $3$ other tiles in the ordering that beforehand it was not. So, the number of inversions must be going up by $3$. And if you put it up again, then the number of inversions decreases by $3$ again. Either way, the parity of the total number of inversions changes from an even number to an odd number, or vice versa."

As your board states indicate, that reasoning is incorrect. Moving N up (the second column move) increases the number of inversions by $1$. I note that the accepted answer followed this same mistake through in its 'proof'.

Of course, what still is true is that the parity changes for any column move: if it was odd before, then it will be even after the move, and vice versa. But a proper proof needs to actually prove that!