\contentsline {chapter}{\numberline {1}Elementary, my dear Watson}{1}{chapter.1}
\contentsline {section}{\numberline {1.1}You have a logical mind if...}{1}{section.1.1}
\contentsline {subsection}{\numberline {1.1.1}`You talking to me?'}{6}{subsection.1.1.1}
\contentsline {section}{\numberline {1.2}Elements, my dear Watson}{7}{section.1.2}
\contentsline {chapter}{\numberline {2}`And you do addition?'}{13}{chapter.2}
\contentsline {section}{\numberline {2.1}Functions}{13}{section.2.1}
\contentsline {section}{\numberline {2.2}Functions on vectors}{20}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}History}{20}{subsection.2.2.1}
\contentsline {subsection}{\numberline {2.2.2}$3\times 3$ matrices}{20}{subsection.2.2.2}
\contentsline {subsection}{\numberline {2.2.3}$m\times n$ matrices}{22}{subsection.2.2.3}
\contentsline {subsection}{\numberline {2.2.4}Multiplication and inverses}{23}{subsection.2.2.4}
\contentsline {subsection}{\numberline {2.2.5}Determinants}{24}{subsection.2.2.5}
\contentsline {section}{\numberline {2.3}Relations}{26}{section.2.3}
\contentsline {section}{\numberline {2.4}Counting and mathematical induction}{29}{section.2.4}
\contentsline {chapter}{\numberline {3}Bell ringing and other permutations}{35}{chapter.3}
\contentsline {section}{\numberline {3.1}Definitions}{35}{section.3.1}
\contentsline {section}{\numberline {3.2}Inverses}{41}{section.3.2}
\contentsline {section}{\numberline {3.3}Cycle notation}{46}{section.3.3}
\contentsline {section}{\numberline {3.4}An algorithm to list all the permutations}{51}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}Why Steinhaus' algorithm works}{53}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}A side order of dessert: cake cutting}{54}{subsection.3.4.2}
\contentsline {section}{\numberline {3.5}Permutations and bell ringing}{54}{section.3.5}
\contentsline {chapter}{\numberline {4}A procession of permutation puzzles}{59}{chapter.4}
\contentsline {section}{\numberline {4.1}15 Puzzle}{60}{section.4.1}
\contentsline {section}{\numberline {4.2}The Hockeypuck puzzle}{61}{section.4.2}
\contentsline {section}{\numberline {4.3}Rainbow Masterball}{62}{section.4.3}
\contentsline {section}{\numberline {4.4}Pyraminx}{66}{section.4.4}
\contentsline {section}{\numberline {4.5}Rubik's Cubes}{67}{section.4.5}
\contentsline {subsection}{\numberline {4.5.1}$2\times 2\times 2$ Rubik's Cube}{67}{subsection.4.5.1}
\contentsline {subsection}{\numberline {4.5.2}$3\times 3\times 3$ Rubik's Cube}{69}{subsection.4.5.2}
\contentsline {subsection}{\numberline {4.5.3}Some two-player Rubik's Cube games}{72}{subsection.4.5.3}
\contentsline {subsubsection}{The superflip game}{72}{section*.2}
\contentsline {section}{\numberline {4.6}Skewb}{73}{section.4.6}
\contentsline {section}{\numberline {4.7}Megaminx}{75}{section.4.7}
\contentsline {section}{\numberline {4.8}Other permutation puzzles}{78}{section.4.8}
\contentsline {chapter}{\numberline {5}What's commutative and purple?}{79}{chapter.5}
\contentsline {section}{\numberline {5.1}The unit quaternions}{80}{section.5.1}
\contentsline {section}{\numberline {5.2}Finite cyclic groups}{81}{section.5.2}
\contentsline {section}{\numberline {5.3}The dihedral group}{82}{section.5.3}
\contentsline {section}{\numberline {5.4}The symmetric group}{83}{section.5.4}
\contentsline {section}{\numberline {5.5}General definitions}{84}{section.5.5}
\contentsline {subsection}{\numberline {5.5.1}The Gordon game}{90}{subsection.5.5.1}
\contentsline {section}{\numberline {5.6}Subgroups}{91}{section.5.6}
\contentsline {section}{\numberline {5.7}Puzzling examples}{93}{section.5.7}
\contentsline {subsection}{\numberline {5.7.1}The superflip}{95}{subsection.5.7.1}
\contentsline {subsection}{\numberline {5.7.2}Example: The two squares group}{96}{subsection.5.7.2}
\contentsline {section}{\numberline {5.8}Commutators}{98}{section.5.8}
\contentsline {section}{\numberline {5.9}Conjugation}{100}{section.5.9}
\contentsline {section}{\numberline {5.10}Orbits and actions}{104}{section.5.10}
\contentsline {section}{\numberline {5.11}Cosets}{109}{section.5.11}
\contentsline {section}{\numberline {5.12}Campanology, revisited}{113}{section.5.12}
\contentsline {section}{\numberline {5.13}Dimino's Algorithm}{114}{section.5.13}
\contentsline {chapter}{\numberline {6}Welcome to the machine}{117}{chapter.6}
\contentsline {section}{\numberline {6.1}Some history}{117}{section.6.1}
\contentsline {section}{\numberline {6.2}Merlin's Machine}{118}{section.6.2}
\contentsline {subsection}{\numberline {6.2.1}The machine}{118}{subsection.6.2.1}
\contentsline {subsection}{\numberline {6.2.2}The rectangular graph}{119}{subsection.6.2.2}
\contentsline {section}{\numberline {6.3}Variants}{119}{section.6.3}
\contentsline {subsection}{\numberline {6.3.1}Merlin's Magic and $3\times 3$ Lights Out}{119}{subsection.6.3.1}
\contentsline {subsection}{\numberline {6.3.2}The Orbix}{119}{subsection.6.3.2}
\contentsline {subsection}{\numberline {6.3.3}Keychain Lights Out}{120}{subsection.6.3.3}
\contentsline {subsection}{\numberline {6.3.4}Lights Out}{120}{subsection.6.3.4}
\contentsline {subsection}{\numberline {6.3.5}Deluxe Lights Out}{120}{subsection.6.3.5}
\contentsline {subsection}{\numberline {6.3.6}Lights Out Cube}{121}{subsection.6.3.6}
\contentsline {subsection}{\numberline {6.3.7}Alien Tiles}{121}{subsection.6.3.7}
\contentsline {subsection}{\numberline {6.3.8}Theoretical generalizations and variants}{121}{subsection.6.3.8}
\contentsline {section}{\numberline {6.4}Finite state machines}{121}{section.6.4}
\contentsline {section}{\numberline {6.5}The mathematics of the machine}{123}{section.6.5}
\contentsline {subsection}{\numberline {6.5.1}The square case}{124}{subsection.6.5.1}
\contentsline {subsection}{\numberline {6.5.2}Downshifting}{126}{subsection.6.5.2}
\contentsline {subsection}{\numberline {6.5.3}The rectangular case}{130}{subsection.6.5.3}
\contentsline {subsection}{\numberline {6.5.4}Alien Tiles again}{130}{subsection.6.5.4}
\contentsline {subsection}{\numberline {6.5.5}Orbix, revisited}{131}{subsection.6.5.5}
\contentsline {subsection}{\numberline {6.5.6}Return of the Keychain Lights Out}{135}{subsection.6.5.6}
\contentsline {chapter}{\numberline {7}`God's algorithm' and graphs}{137}{chapter.7}
\contentsline {section}{\numberline {7.1}In the beginning...}{137}{section.7.1}
\contentsline {section}{\numberline {7.2}Cayley graphs}{139}{section.7.2}
\contentsline {section}{\numberline {7.3}God's algorithm}{142}{section.7.3}
\contentsline {section}{\numberline {7.4}The graph of the 15 Puzzle}{144}{section.7.4}
\contentsline {subsection}{\numberline {7.4.1}General definitions}{145}{subsection.7.4.1}
\contentsline {subsection}{\numberline {7.4.2}Remarks on applications}{148}{subsection.7.4.2}
\contentsline {chapter}{\numberline {8}Symmetry and the Platonic solids}{149}{chapter.8}
\contentsline {section}{\numberline {8.1}Descriptions}{149}{section.8.1}
\contentsline {section}{\numberline {8.2}Background on symmetries in 3-space}{150}{section.8.2}
\contentsline {section}{\numberline {8.3}Symmetries of the tetrahedron}{153}{section.8.3}
\contentsline {section}{\numberline {8.4}Symmetries of the cube}{154}{section.8.4}
\contentsline {section}{\numberline {8.5}Symmetries of the dodecahedron}{155}{section.8.5}
\contentsline {section}{\numberline {8.6}Some thoughts on the icosahedron}{157}{section.8.6}
\contentsline {section}{\numberline {8.7}$901,083,404,981,813,616$ cubes}{159}{section.8.7}
\contentsline {chapter}{\numberline {9}The illegal cube group}{161}{chapter.9}
\contentsline {section}{\numberline {9.1}Functions between two groups}{162}{section.9.1}
\contentsline {section}{\numberline {9.2}Group actions}{165}{section.9.2}
\contentsline {section}{\numberline {9.3}When two groups are really the same}{166}{section.9.3}
\contentsline {subsection}{\numberline {9.3.1}Conjugation in $S_n$}{169}{subsection.9.3.1}
\contentsline {subsection}{\numberline {9.3.2}... and a side order of automorphisms, please}{170}{subsection.9.3.2}
\contentsline {section}{\numberline {9.4}Kernels are normal, some subgroups are not}{171}{section.9.4}
\contentsline {subsection}{\numberline {9.4.1}The alternating group}{173}{subsection.9.4.1}
\contentsline {section}{\numberline {9.5}Quotient groups}{173}{section.9.5}
\contentsline {section}{\numberline {9.6}Dabbling in direct products}{176}{section.9.6}
\contentsline {subsection}{\numberline {9.6.1}First fundamental theorem of cube theory}{177}{subsection.9.6.1}
\contentsline {subsection}{\numberline {9.6.2}Example: cube twists and flips}{178}{subsection.9.6.2}
\contentsline {subsection}{\numberline {9.6.3}Example: the slice group of the cube}{179}{subsection.9.6.3}
\contentsline {subsection}{\numberline {9.6.4}Example: the slice group of the Megaminx}{183}{subsection.9.6.4}
\contentsline {section}{\numberline {9.7}A smorgasbord of semi-direct products}{183}{section.9.7}
\contentsline {section}{\numberline {9.8}A reification of wreath products}{187}{section.9.8}
\contentsline {subsection}{\numberline {9.8.1}The illegal Rubik's Cube group}{188}{subsection.9.8.1}
\contentsline {subsection}{\numberline {9.8.2}Elements of order $d$ in $C_m\tmspace +\thinmuskip {.1667em}{\rm wr}\tmspace +\thinmuskip {.1667em} S_n$}{189}{subsection.9.8.2}
\contentsline {chapter}{\numberline {10}Words which move}{191}{chapter.10}
\contentsline {section}{\numberline {10.1}Words in free groups}{192}{section.10.1}
\contentsline {subsection}{\numberline {10.1.1}Length}{193}{subsection.10.1.1}
\contentsline {subsection}{\numberline {10.1.2}Trees}{195}{subsection.10.1.2}
\contentsline {section}{\numberline {10.2}The word problem}{195}{section.10.2}
\contentsline {section}{\numberline {10.3}Presentations and Plutonian robots}{198}{section.10.3}
\contentsline {section}{\numberline {10.4}Generators, relations for groups of order $<26$}{200}{section.10.4}
\contentsline {section}{\numberline {10.5}The presentation problem}{206}{section.10.5}
\contentsline {subsection}{\numberline {10.5.1}A presentation for $C_m^n \rtimes S_{n+1}$}{206}{subsection.10.5.1}
\contentsline {subsection}{\numberline {10.5.2}Idea of the proof}{208}{subsection.10.5.2}
\contentsline {chapter}{\numberline {11}The (legal) Rubik's Cube group}{211}{chapter.11}
\contentsline {section}{\numberline {11.1}Mathematical description of moves}{211}{section.11.1}
\contentsline {subsection}{\numberline {11.1.1}Notation}{211}{subsection.11.1.1}
\contentsline {subsection}{\numberline {11.1.2}Corner orientations}{213}{subsection.11.1.2}
\contentsline {subsection}{\numberline {11.1.3}Edge orientations}{214}{subsection.11.1.3}
\contentsline {subsection}{\numberline {11.1.4}The semi-direct product}{215}{subsection.11.1.4}
\contentsline {section}{\numberline {11.2}Structure of the cube group}{216}{section.11.2}
\contentsline {subsection}{\numberline {11.2.1}Second fundamental theorem of cube theory}{216}{subsection.11.2.1}
\contentsline {subsection}{\numberline {11.2.2}Some consequences}{219}{subsection.11.2.2}
\contentsline {section}{\numberline {11.3}The moves of order 2}{221}{section.11.3}
\contentsline {chapter}{\numberline {12}Squares, two-faces, and other subgroups}{225}{chapter.12}
\contentsline {section}{\numberline {12.1}The squares subgroup}{225}{section.12.1}
\contentsline {section}{\numberline {12.2}Fast-forwarding though finite fields}{228}{section.12.2}
\contentsline {subsection}{\numberline {12.2.1}The general definition}{228}{subsection.12.2.1}
\contentsline {subsection}{\numberline {12.2.2}A construction of $\@mathbb {F}_p$}{229}{subsection.12.2.2}
\contentsline {subsection}{\numberline {12.2.3}A construction of finite fields}{229}{subsection.12.2.3}
\contentsline {section}{\numberline {12.3}$PGL(2,\@mathbb {F}_5)$ and two faces of the cube}{232}{section.12.3}
\contentsline {subsection}{\numberline {12.3.1}M\"obius transformations}{233}{subsection.12.3.1}
\contentsline {subsection}{\numberline {12.3.2}The main isomorphism}{235}{subsection.12.3.2}
\contentsline {subsection}{\numberline {12.3.3}The labeling}{236}{subsection.12.3.3}
\contentsline {subsection}{\numberline {12.3.4}Proof of the second theorem}{237}{subsection.12.3.4}
\contentsline {section}{\numberline {12.4}The cross groups}{238}{section.12.4}
\contentsline {subsection}{\numberline {12.4.1}$PSL(2,\@mathbb {F}_7)$ and crossing the cube}{239}{subsection.12.4.1}
\contentsline {subsection}{\numberline {12.4.2}Klein's 4-group and crossing the Pyraminx}{241}{subsection.12.4.2}
\contentsline {chapter}{\numberline {13}Other Rubik-like puzzle groups}{243}{chapter.13}
\contentsline {section}{\numberline {13.1}A uniform approach}{243}{section.13.1}
\contentsline {subsection}{\numberline {13.1.1}General remarks}{244}{subsection.13.1.1}
\contentsline {subsection}{\numberline {13.1.2}Parity conditions}{244}{subsection.13.1.2}
\contentsline {section}{\numberline {13.2}On the group structure of the Skewb}{245}{section.13.2}
\contentsline {section}{\numberline {13.3}Mathematical description of the $2\times 2\times 2$ cube}{249}{section.13.3}
\contentsline {section}{\numberline {13.4}On the group structure of the Pyraminx}{250}{section.13.4}
\contentsline {subsection}{\numberline {13.4.1}Orientations}{252}{subsection.13.4.1}
\contentsline {subsection}{\numberline {13.4.2}Center pieces}{254}{subsection.13.4.2}
\contentsline {subsection}{\numberline {13.4.3}The group structure}{254}{subsection.13.4.3}
\contentsline {section}{\numberline {13.5}The homotopy group of the Square 1 puzzle}{255}{section.13.5}
\contentsline {subsection}{\numberline {13.5.1}The main result}{255}{subsection.13.5.1}
\contentsline {subsection}{\numberline {13.5.2}Some notation}{256}{subsection.13.5.2}
\contentsline {subsection}{\numberline {13.5.3}Two subgroups}{258}{subsection.13.5.3}
\contentsline {subsection}{\numberline {13.5.4}Proof of the theorem}{258}{subsection.13.5.4}
\contentsline {section}{\numberline {13.6}The Masterball group}{259}{section.13.6}
\contentsline {chapter}{\numberline {14}Crossing the Rubicon}{261}{chapter.14}
\contentsline {section}{\numberline {14.1}Doing the Mongean shuffle}{261}{section.14.1}
\contentsline {section}{\numberline {14.2}Background on $PSL_2$}{263}{section.14.2}
\contentsline {section}{\numberline {14.3}Galois' last dream}{264}{section.14.3}
\contentsline {section}{\numberline {14.4}The $M_{12}$ generation}{264}{section.14.4}
\contentsline {section}{\numberline {14.5}Coding the Golay way}{265}{section.14.5}
\contentsline {section}{\numberline {14.6}$M_{12}$ is crossing the Rubicon}{272}{section.14.6}
\contentsline {section}{\numberline {14.7}An aside: A pair of cute facts}{272}{section.14.7}
\contentsline {subsection}{\numberline {14.7.1}Hadamard matrices}{273}{subsection.14.7.1}
\contentsline {subsection}{\numberline {14.7.2}$5$-transitivity}{275}{subsection.14.7.2}
\contentsline {chapter}{\numberline {15}Some solution strategies}{277}{chapter.15}
\contentsline {section}{\numberline {15.1}A strategy for solving the Rubik's Cube}{277}{section.15.1}
\contentsline {subsection}{\numberline {15.1.1}Strategy for solving the cube}{278}{subsection.15.1.1}
\contentsline {subsection}{\numberline {15.1.2}Catalog of $3\times 3$ Rubik's `supercube' moves}{280}{subsection.15.1.2}
\contentsline {section}{\numberline {15.2}The subgroup method}{280}{section.15.2}
\contentsline {subsection}{\numberline {15.2.1}Example: the corner-edge method}{281}{subsection.15.2.1}
\contentsline {subsection}{\numberline {15.2.2}Example: Thistlethwaite's method}{282}{subsection.15.2.2}
\contentsline {subsection}{\numberline {15.2.3}Example: Kociemba's method}{282}{subsection.15.2.3}
\contentsline {section}{\numberline {15.3}Rainbow Masterball}{283}{section.15.3}
\contentsline {subsection}{\numberline {15.3.1}A catalog of Masterball moves}{284}{subsection.15.3.1}
\contentsline {subsubsection}{Column moves}{284}{section*.3}
\contentsline {subsubsection}{Some products of 2-cycles on the facets}{285}{section*.4}
\contentsline {section}{\numberline {15.4}The Skewb}{286}{section.15.4}
\contentsline {subsection}{\numberline {15.4.1}Strategy}{286}{subsection.15.4.1}
\contentsline {subsection}{\numberline {15.4.2}A catalog of Skewb moves}{286}{subsection.15.4.2}
\contentsline {section}{\numberline {15.5}The Pyraminx}{287}{section.15.5}
\contentsline {section}{\numberline {15.6}The Megaminx}{288}{section.15.6}
\contentsline {subsection}{\numberline {15.6.1}Catalog of moves}{288}{subsection.15.6.1}
\contentsline {chapter}{\numberline {16}Coda: Questions and other directions}{289}{chapter.16}
\contentsline {section}{\numberline {16.1}Coda}{289}{section.16.1}