0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The following article may be of help: The Fifteen Puzzle - A New Approach, Mathematics Magazine (Mathematical Association of America), Vol 90, No 1, February 2017, pp 48-57. $\endgroup$ – user348749 Jul 11 '17 at 10:22
  • $\begingroup$ For your first question: what is the parity of the number of inversions due to an exchange of a single pair of tiles? $\endgroup$ – Tob Ernack Jul 11 '17 at 10:31
  • $\begingroup$ @TobErnack If I exchange a single pair of tiles, like switching their position, I either create a new inversion if they have been in order before or I "fix" an inversion if they have been inverted before, no? So exchanging a single pair of tile switches the parity of the number of inversions to the opposite. $\endgroup$ – Max Jul 12 '17 at 5:20
  • $\begingroup$ @TobErnack Oh I get it, if the number of inversions in the start state is odd, we must make an odd number of column moves to get to an even number of inversions. Can you give me a hint how to interpret So after an odd number of column moves, the blank can not pos- sibly be back in the last row, where it belongs!? $\endgroup$ – Max Jul 12 '17 at 5:26
  • $\begingroup$ Ok, I think I get it now, in the desired state the blank square is in the bottom right in row 4 (where it also resides in the starting position). Each column move changes the row number of the blank square +1 or -1. So after an odd number of moves it can't be in an even row number. Sorry, I think I made the question much harder buy not realizing they were taking about this specific starting position and make observations based on that. I was thinking too far ahead. Maybe I should try to come up with an answer for my own question for future reference later. $\endgroup$ – Max Jul 12 '17 at 5:38
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.