[Math] 15 Puzzle question – trying to understand reasoning here

alternative-proofdiscrete mathematicsproof-explanation

I'm following some problem about the 15 puzzle from the MIT Discrete Maths course. They are talking about this starting position:

1. row     A B C D
2. row     E F G H
3. row     I J K L
4. row     M O N

Where there is exactly one inversion (O and N).

I figured out some questions on my own:

a) Can a row move change the order of tiles?

My answer: A row move can change the index of the tile moved only my going left -1 or going right +1. As no other tile moves, the order of tiles overall doesn't change.

b) How many pairs of tiles will have their relative order changed by a column move.

My answer: In a column move we either move the tile down a column, sliding it after the next 3 tiles or up one column, sliding it before the previous 3 tiles. Thus a column move changes the relative order of exactly 3 tiles.

c) What effect does a row move have on the parity of inversions?

My answer: As described in a) the order of tiles doesn't change in a row move, therefore the parity of inversions stays unchanged for a row move.

d) What effect does a column move have on the parity of number of inversions

e) The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles (N and O, say). But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs!

I tried playing around and for d) I claim that: a column move changes the parity of the number of inversions $n$ by either +3 or -3, always flipping the parity $n$ to the opposite side (even $n$ becomes odd, odd $n$ becomes even after a column move.)

The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles

I don't understand this sentence. Why?

EDIT: After reading the problem again, and taking into account they talk about the start state which has an odd number (1) of inversions, it makes more sense now. We need to go to an even number of inversions (0) by making an odd number of column moves, as each column move flips the parity to the oppsite side, see d)

But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs!

Hm, why not? I still dont' get what they mean with So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs.

Best Answer

Theorem. No sequence of moves transforms the board below on the left into the board below on the right.

1. row     A B C D                 A B C D 
2. row     E F G H                 E F G H
3. row     I J K L                 I J K L
4. row     M O N                   M N O

a) Can a row move change the order of the tiles?

A row move can change the position of a tile only +1 or -1, but the position of no other tile changes. So a row move can never change the order of tiles.

b) How many pairs of tiles will have their relative order changed by a column move?

A column move changes the order of a tile either -4 or +4. When the tile is moved down, it moves in front of the next 3 tiles. When the tile is moved up, it moves behind the previous 3 tiles. Hence a column move changes the relative order for 3 pairs of tiles.

c) We define an inversion to be a pair of letters L1 and L2 for which L1 precedes L2 in the alphabet, but L1 appears after L2 in the order of the tiles.. What effect does a row move have on the parity of the number of inversions??

As a row move doesn't change the order of tiles, a row move has no effect on the number of inversions, so the parity stays the same.

d) What effect does a column move have on the parity of the number of inversions? Prove your answer.

As a column move changes relative order of 3 tiles, the number of inversions is flipped to the opposite, from even to odd and from odd to even.

e) The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles (N and O, say). But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs! Now we can bundle up all these observations and state an invariant, a property of the puzzle that never changes, no matter how you slide the tiles around.

Lemma: In every configuration reachable from the position shown below, the parity of the number of inversions is different from the parity of the row containing the blank square.

1. row     A B C D                  
2. row     E F G H                 
3. row     I J K L                 
4. row     M O N

Proof of the lemma by induction:

Base case:

After 0 moves, there is exactly 1 inversion (odd) and the row number of the blank square is 4 (even).

Inductive step:

If a row move happens, the row number of the blank square doesn't change, neither does the number of inversions change.

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.

e) Prove the theorem that we originally set out to prove.

As per the lemma, the parity of the number of inversions will always be different from the parity of the the row number for the blank square. In the desired end state their parity is equal, which will never be possible given the start state where those two variables have different parity.

Related Question