Problem 1: The 15 puzzle revisited Grading criteria: code correctness for a and b; mathematical correctness for c. Part d is optional. a. Construct a graph I representing the spaces of a 4 x 4 grid, with the vertices labeled A E I M B F J N C G K O D H L P in which two vertices are joined by an edge if the corresponding squares of the grid share a side (not just a corner). In [ ]: b. Form the symmetric group G on the symbols A through P. (Note: for l a list, SymmetricGroup(l) gives the group of permutations acting on l.) Let S be the subset of G consisting of the transpositions of the form (XY) for each edge {X, Y} in 1. Verify that S generates G. In [ ]: c. Find a subset T of S of smallest possible size such that T does in fact generate G. You should verify (computationally) that T generates G, and explain (mathematically) why no smaller set can work. (Hint for the second part: argue in terms of the graph T.) In [ ]: Problem 1: The 15 puzzle revisited Grading criteria: code correctness for a and b; mathematical correctness for c. Part d is optional. a. Construct a graph I representing the spaces of a 4 x 4 grid, with the vertices labeled A E I M B F J N C G K O D H L P in which two vertices are joined by an edge if the corresponding squares of the grid share a side (not just a corner). In [ ]: b. Form the symmetric group G on the symbols A through P. (Note: for l a list, SymmetricGroup(l) gives the group of permutations acting on l.) Let S be the subset of G consisting of the transpositions of the form (XY) for each edge {X, Y} in 1. Verify that S generates G. In [ ]: c. Find a subset T of S of smallest possible size such that T does in fact generate G. You should verify (computationally) that T generates G, and explain (mathematically) why no smaller set can work. (Hint for the second part: argue in terms of the graph T.) In [ ]