Permutation Puzzles. A Mathematical Perspective

Description

http://www.sfu.ca/~jtmulhol/math302/# Part I — Part One: Foundations 1 Permutation Puzzles 1.1 Introduction 1.2 A Collection of Puzzles 1.3 Which brings us to the Definition of a Permutation Puzzle 1.4 Exercises 2 A Bit of Set Theory 2.1 Introduction 2.2 Sets and Subsets 2.3 Laws of Set Theory 2.4 Examples Using SageMath 2.5 Exercises Part II — Part Two: Permutations 3 Permutations 3.1 Permutation: Preliminary Definition 3.2 Permutation: Mathematical Definition 3.3 Composing Permutations 3.4 Associativity of Permutation Composition 3.5 Inverses of Permutations 3.6 The Symmetric Group Sn 3.7 Rules for Exponents 3.8 Order of a Permutation 3.9 Exercises 4 Permutations: Cycle Notation 4.1 Permutations: Cycle Notation 4.2 Products of Permutations: Revisited 4.3 Properties of Cycle Form 4.4 Order of a Permutation: Revisited 4.5 Inverse of a Permutation: Revisited 4.6 Summary of Permutations 4.7 Working with Permutations in SageMath 4.8 Exercises 5 From Puzzles To Permutations 5.1 Introduction 5.2 Swap 5.3 15-Puzzle 5.4 Oval Track Puzzle 5.5 Hungarian Rings 5.6 Rubik's Cube 5.7 Exercises 6 Permutations: Products of 2-Cycles 6.1 Introduction 6.2 Product of 2-Cycles 6.3 Solvability of Swap 6.4 Exercises 7 Permutations: The Parity Theorem 7.1 Introduction 7.2 Variation of Swap 7.3 Proof of the Parity Theorem 7.4 Exercises 8 Permutations: An and 3-Cycles 8.1 Swap Variation: A Challenge 8.2 The Alternating Group An 8.3 Products of 3-cycles 8.4 Variations of Swap: Revisited 8.5 Exercises 9 The 15-Puzzle 9.1 Solvability Criteria 9.2 Proof of Solvability Criteria 9.3 Strategy for Solution 9.4 Exercises Part III — Part Three: Group Theory 10 Groups 10.1 Group: Definition 10.2 Some Everyday Examples of Groups 10.3 Further Examples of Groups 10.4 Exercises 11 Subgroups 11.1 Subgroups 11.2 Examples of Subgroups 11.3 The Center of a Group 11.4 Lagrange's Theorem 11.5 Cyclic Groups Revisited 11.6 Cayley's Theorem 11.7 Exercises 12 Puzzle Groups 12.1 Puzzle Groups 12.2 Rubik's Cube 12.3 Hungarian Rings 12.4 15-Puzzle 12.5 Exercises 13 Commutators 13.1 Commutators 13.2 Creating Puzzle moves with Commutators 13.3 Exercises 14 Conjugates 14.1 Conjugates 14.2 Modifying Puzzle moves with Conjugates 14.3 Exercises 15 The Oval Track Puzzle 15.1 Oval Track with T=(14)(23) 15.2 Variations of the Oval Track T move 15.3 Exercises 16 The Hungarian Rings Puzzle 16.1 Hungarian Rings - Numbered version 16.2 Building Small Cycles: Tools for Our End-Game Toolbox 16.3 Solving the end-game 16.4 Hungarian Rings - Coloured version 16.5 Exercises 17 Partitions & Equivalence Relations 17.1 Partitions of a Set 17.2 Relations 17.3 Equivalence Relation 17.4 Exercises 18 Cosets & Lagrange's Theorem 18.1 Cosets 18.2 Lagrange's Theorem 18.3 Exercises Part IV — Part Four: Rubiks' Cube 19 Rubik's Cube: Beginnings 19.1 Rubik's Cube terminology and notation 19.2 Impossible Moves 19.3 A Catalog of Basic Move Sequences 19.4 Strategy for Solution 19.5 Exercises 20 Rubik's Cube: The Fundamental Theorem 20.1 Rubik's Cube - A Model 20.2 The Fundamental Theorem of Cubology 20.3 When are two assembled cubes equivalent? 20.4 Exercises 21 Rubik's Cube: Subgroups of the Cube Group 21.1 Building Big Groups from Smaller Ones 21.2 Some Subgroups of RC3 21.3 Structure of the Cube Group RC3 21.4 Exercises Part V — Part Five: Symmetry & Counting 22 The Orbit-Stabilizer Theorem 22.1 Orbits & Stabilizers 22.2 Permutations Acting on Sets: Application of the Orbit-Stabilizer Theorem 22.3 Exercises 23 Burnside's Theorem 23.1 A Motivating Example 23.2 Burnside's Theorem 23.3 Applications of Burnside's Theorem 23.4 Exercises Part VI — Part Six: Light's Out 24 Lights Out 24.1 Lights Out 24.2 Lights Out: A Matrix Model 24.3 Summary of 55 lights out puzzle 24.4 Eigenvalues and Eigenvectors 24.5 Other sized game boards 24.6 Light-Chasing Strategy 24.7 Exercises Part VII — Appendix A SageMath A.1 SageMath Basics A.2 Variables and Statements A.3 Lists A.4 Sets A.5 Commands/Functions A.6 if, while, and for statements A.7 Exercises B Basic Properties of Integers B.1 Divisibility and the Euclidean Algorithm B.2 Prime Numbers B.3 Euler's -function B.4 Modular Arithmetic B.5 Exercises Bibliography Articles Books Web Sites Index