Question

b+c

ced in a 4x4 grid, as shown below left. A 12. Consider a puzzle consisting of fifteen numbered squares pla move consists of sliding a numbered square into the adjacent unoccupied square. 13 9 10 11 12 13 1514 13 1415 If we treat the unoccupied square as numbered 16, every configuration corresponds to a permutation in S16. For example, the initial configuration on the left corresponds to the identity, while the configuration in the middle corresponds to the permutation (1 2714 11 123 16 15 4 13 8 5) (6) (9 10). This permutation sends 7 to 14 because the square numbered 14 is in the position occupied by 7 in the initial configuration. (a) Show that applying a move to a configuration corresponds to composing the corresponding permu- tation with a transposition. (b) Prove that if the unoccupied square starts and ends in the bottom-right corner, then an even number of moves must have occurred. (Hint. Show that the unoccupied square moved up the same number of times that it moved down.) (c) Hence, deduce that it is impossible to start with the initial configuration on the left and end up with the configuration on the right, in which the squares numbered 14 and 15 are swapped.

Answer 1

Le ome baik to the Sane cell what have ut dose a 3T once and doum once Cnove 1) it Dn move ot eura. ves rsvneeven nunber way is swieppi onte ns1s which in trn is an odd mare So, we have dedusad that he iea Cen't Le OnC& K M 0