MATHEMATICS OF THE RUBIK'S CUBE
Fall 1996 course at the
US Naval Academy
Annapolis, MD
Instructor:
Assoc Prof W. D. Joyner
office: Ch 328
phone: (410)293-6738
email: wdj@sma.usna.navy.mil or wdj@nadn.navy.mil
Mathematical Quotes:
"By and large it is uniformly true that in mathematics that there is
a time lapse between a mathematical discovery and the moment it
becomes useful; and that this lapse can be anything from 30 to 100
years, in some cases even more; and that the whole system seems to
function without any direction, without any reference to usefulness,
and without any desire to do things which are useful."
John von Neumann
COLLECTED WORKS, VI, p489
"[Lefschetz and Einstein] had a running debate for many years.
Lefschetz insisted that there was difficult mathematics. Einstein said
that there was no difficult mathematics, only stupid mathematicians.
I think that the history of mathematics is on the side of Einstein."
Richard Bellman
EYE OF THE HURRICANE, 1984
"The advantage is that mathematics is a field in which one's blunders
tend to show very clearly and can be corrected or erased with a stroke of
the pencil. It is a field which has often been compared with chess, but
differs from the latter in that it is only one's best moments that count
and not one's worst."
Norbert Wiener
EX-PRODIGY: MY CHILDHOOD AND YOUTH
For more quotes, see [M], [S] or the www page at
http://math.furman.edu/~mwoodard/mquot.html
Course Outline
Introduction
0. Logic and sets
1. Functions on finite sets
injective fcns, surjective fcns
2. Permutations
inverse permutations and even, odd permutations
3. Permutation puzzles
* 15 puzzle
* devil's circles
* equator
* masterball
* 2x2 Rubik's cube
* 3x3 Rubik's cube
* 4x4 Rubik's cube
* megaminx
4. Groups, I
symmetric group of a finite set, permutation groups, basic terms
(subgroups, order, conjugates, commutators)
5. Orbits, actions, and cosets
basic definitions (free and transitive actions, stabilizers),
relationship between orbit and stabilizer
6. Strategies
solution strategy and special moves for
* 3x3 cube
* 4x4 cube
* rainbow masterball
Appendix: A catalog of Rubik's cube moves
7. Cayley graphs and God's algorithm
A graphical interpretation of a solution of a permutation
puzzle
8. Symmetry groups of the Platonic solids
* background on isometries of 3-space
* the tetrahedral group
* the octahedral group
* the icosahedral group
(orders, stabilizer subgroups, and description of symmetries)
9. Groups, II
homomorphisms, the homomorphism theorems, normal subgroups,
kernels, direct products, semi-direct products, wreath
products
10. Structure of the Rubik's cube group
orientation conditions
11. Rubika Esoterica
12. Advanced topic: Realizing PGL(2,F5) inside the Rubik's
cube group
References
Notation
N = {1,2,...} = the set of natural numbers,
Z = {...,-2,-1,0,1,2,...} = the set of integers
Let S, T be finite sets.
"s in S" means s belongs to S
"S subset T" means S is a subset of T
SxT = {(s,t) | s in S and t in T}
= set of all pairs of the form (s,t) such that
s belongs to S and t belongs to T
= Cartesian product of S and T,
S union T = {x | x in S or x in T}
= the set of all elements of S or T
= the union of S and T,
S intersection T = {x | x in S and x in T}
= the set of all elements belonging to both S and T
= the intersection of S and T,
|S| = #S = the number of distinct elements in S.
"S <> T" means S does not equal T
In general, we shall use double quotes around a word we are defining,
an underscore "_" will usually indicate a subscript and a caret "^"
will usually denote a superscript.
INTRODUCTION
Groups measure symmetry and nowhere is this more evident than
in the study of symmetry in 2- and 3-dimensional geometric figures.
The Rubik's cube, and related puzzles, manifest this symmetry in
a manipulation puzzle.
This is a course about creating a group-theoretical model of
Rubik's cube-like puzzles. In other words, we will use group
theory to learn as much as we reasonably can (given the limitations
of the course) about these types of permutation puzzles. What we
need from group theory will, for the most part, be proven and all
that is really required from the student is a certain amount
of mathematical sophistication, energy, and some geometrical intuition.
The ulterior motive for this course (and there is one) is to
teach some group theory. If there is a different slant to our
approach compared to others it is that we've stressed example. There
is also an attempt to present some of the basic notions
algorithmically (as in [Bu]), consistent with our concrete
point of view.
Group theory is one of those topics which occurs in a
surprisingly large variety of seemingly disparate situations.
Basically, any time there is symmetry, don't be surprised if
there is a group hiding in the background. The Rubik's cube
has a lot of symmetry but so do lots of other things -
crystallography, elementary particle physics, to name just a few.
As Hilbert said, the art to doing mathematics is to pick a
good example to learn from. Hopefully, the Rubik's cube will be
a good example.
How much group theory do we hope to teach you? This course,
if successful, should prepare you to study more group theory from one
of the standard group theory texts, say Rotman [R]. This course
covers the material in most of chapter 1, parts of chapters 2 and
3 in [R]. We shall assume, in some of the later chapters, some
familiarity with matrices (matrix multiplication, transposes,
some properties of the determinant and the inverse matrix). This
course, with a course in linear algebra, will give the student
more than enough background to begin reading Rotman [R].
I thank Dan Bump, Micheal Fourte, Mark Meyerson, and Andrew
Southern for their suggestions on this material.