Math E-320: Spring 2012

Teaching Math with a Historical Perspective

Mathematics E-320: The floppy

Instructor: Oliver Knill

Office: SciCtr 432

Email: knill@math.harvard.edu

The floppy puzzle consists of one third of the Rubic cube.
It is a wonderful example to show the concept of groups since
it does not have the complexity of the Rubik cube (*)
On the other hand, we can teach and learn the solution to the floppy in 10 minutes.
The group has 192 = 4! * 2^{3} elements and is so
small enough that we can also visualize the Cayley graph
which is the graph showing all configurations as nodes.
Two nodes are connected if there is a move which maps a
configuration to the other, where a move is an flip.
Below you see the a visualization of the Cayley graph of the floppy
computed in Mathematica. Because the group is so small, it can be kept as a whole in the computer. We can measure things out like the diameter. The diameter of the floppy is 6. You can with 6 moves reach from any position to any other position. This is the "God's number for the floppy". The corresponding question for the Rubik cube was solved only in 2010. The Rubik cube has 43'252'003'274'489'856'000 positions. A computer can not hold all of them in memory. Still it is today known that the diameter is 20. It is known to be the God number. |

- I had spent as a teenager 3 pretty intense weeks alone
to find a method for solving the Rubik cube from scratch. For any of the puzzles
I would have the puzzle constantly with me and even play with it while walking from
one place to an other. It needs
**lots of time**to find a solution without help. It is interesting that young kids are in general faster than adults in finding the solution. I had not known group theory then but still today, a mathematician knowing group theory needs quite some time to figure out a method of solution, even with assistance of a computer, because finding the solution moves needs experimentation. - As an undergraduate student, I had been a course assistant for a computer laboratory.
One of the project assigned to the students in the course had been to write a computer
program which would find the
**solution strategy**of the Rubik cube. Note that this is much more difficult than implementing a given solution in the computer. It is an artificial intelligence project since one asks the computer to be creative and find a puzzle strategy. We used the computer algebra system Cayley which is now called Magma. There is an open source program "Gap" which can do similar things today. - As a graduate student, I had participated in a contest in the Swiss town of Bern. A "Rubik cube" type puzzle, the "master ball" had to be solved competitively in front of a larger audience. The task had been to race doing a specific transposition in that group. Having been trained at ETH in algebra and theoretical computer science also been a course assistant in a course using computer algebra, I had used the computer algebra system Cayley (now Magma) to find a solution and assigned a Sun workstation to tackle the problem. After a few hours, it came up with a solution which consisted of several dozen moves. I brought this solution to the competition: after all the contestants had been introduced, we went on to race who would solve the puzzle first. The fastest solver was a farmer and cheese-maker from Emmental. Without computers and without any knowledge in group theory, he had the best understanding to walk around in that non-Abelian group. This event happened before the movie "Good Will Hunting" appeared and is no fiction.
- In graduate school, I once gave a seminar talk about the diameter of the Rubik cube. At that time one had known that 18 is a lower bound and 52 is an upper bound. I still remember that one of the commentaries of the seminar was that finding the diameter of the Rubik cube "is not a particularly interesting question".

Please send questions and comments to knill@math.harvard.edu