Problem 2. In the 15-puzzle, there are 15 lettered tiles and a blank square arranged in a 4 x 4 grid. Any lettered tile adjacent to the blank square can be slid into the blank. For example, a sequence of two moves is illustrated below ABCD E FGH In the leftmost configuration shown above, the O and N tiles are out of order. Using only legal moves, is it possible to swap the N and the O, while leaving all the other tiles in their original position and the blank in the bottom right corner? In this problem, you will prove the answer is "no". Theorem 1.1. No sequence of moves transforms the board below on the left into the board below on the right. MNO a) (4 pts) We define the "order" of the tiles in a board to be the sequence of tiles on the board reading from the top row to the bottom row and from left to right within a row. For example, in the right board depicted in the above theorem, the order of the tiles is A, B, C, D, E, etc. Can a row move change the order of the tiles? Prove your answer b) (4 pts) How many pairs of tiles will have their relative order changed by a column move? More formally, for how many pairs of letters L1 and L will L1 appear earlier in the order of the tiles than L2 before the column move and later in the order after the column move? Prove your answer correct c) (4 pts) We define an inversion to be a pair of letters L and L2 for which L1 precedes L2 in the appears after L2 in the order of the tiles. For example, consider the following alphabet, but L on: There are exactly four inversions in the above configuration: E and D, H and G, H and F, and G and F What effect does a row move have on the parity of the number of inversions? Prove your answer d) (8 pts) What effect does a column move have on the parity of the number of inversions? Prove vour answer. e) (16 pts) 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 1.2. In every configuration reachable from the position shown below, the parity of the number of inversions is different from the parity of the Tou) containing the blank square 1 . row 1 row 2 row 3 row EFGH Prove this lemma f) (4 pts) Prove the theorem that we originally set out to prove. So the configuration shown here has one (an odd number) version, (O, N), and the blank square is in row 4 (an even number). The parity of the number of inversions is therefore different from the parity of the row containing the blank square