You are currently browsing the tag archive for the ‘disjoint cycle decomposition’ tag.

In the television show Futurama, episode “The Prisoner of Benda,” Dr. Farnsworth created a machine that swaps the minds of two individuals. Unfortunately, they discover that the machine cannot be used on the same pair of bodies again.

The question is, given a collection of jumbled up minds and bodies, how can you get them all back to normal? Well, they have to come up with some equation to prove that, with enough people switching, eventually everyone will end up in their rightful form.

It was first mentioned in an interview that head writer and executive producer David X. Cohen gave to the American Physical Society:

“In an APS News exclusive, Cohen reveals for the first time that in the 10th episode of the upcoming season, tentatively entitled “The Prisoner of Benda,” a theorem based on group theory was specifically written (and proven!) by staffer/PhD mathematician Ken Keeler to explain a plot twist. Cohen can’t help but chuckle at the irony: his television-writing rule is that entertainment trumps science, but in this special case, a mathematical theorem was penned for the sake of entertainment.”

This theorem is now known as Keeler’s Theorem, or the “Futurama Theorem”.

The Futurama Theorem proves that no matter the size of the collection or how many mind swaps have been made, all minds can be restored to their original bodies using only two extra “clean” bodies (individuals who haven’t swapped minds with anyone) are needed, since a collection of just two people with swapped minds could never get back to normal.

If you want to know more about the details on group theory (group, the symmetric group, permutation diagrams, transpositions, cycle notation, products of disjoint cycles, products of distinct transpositions, etc.) read the talk given by Dana C. Ernst about the Futurama Theorem. He has blogged twice on this talk:
1. Talk about the Futurama Theorem
2. Another talk about the Futurama Theorem

and he has given the talk three times:
1. November 3, 2011 Gordon Talk
2. December 7, 2011 PSU Talk
3. February 28, 2012 UNO Talk

I personally like the first talk. He mentions:

“The slides for the second talk are very similar to the first set, but there are a few differences:

• The second talk is shorter. I trimmed a few things from the first talk that were not completely necessary.
• I’ve improved the wording in a few spots.
• In the second talk, multiplication of permutations is right to left.”

Talks 2 and 3 are almost identical.

If you read the talk, you will understand the proof that appeared in the show,

which uses nothing other than basic facts about group theory and permutations. Furthermore, you will understand applying the algorithm to the arrangement of minds in Futurama requires 13 moves. However, since Fry and Zoiberg only swapped with each other and since there is only one other cycle, we could use Fry and Zoiberg as $x$ and $y$, respectively in the algorithm and thus it only requires 9 moves.

Below are the implementations of the 13 move algorithm in Sage and WolframAlpha. (Note, Sage and WolframAlpha will multiply cycles left to right):
 S_11 = SymmetricGroup(11) c7 = S_11("(1,2,3,4,5,6,7)") c1 = S_11("(8,9)") t1 = S_11("(8,10)") t2 = S_11("(9,11)") t3 = S_11("(9,10)") t4 = S_11("(8,11)") t5 = S_11("(10,1)") t6 = S_11("(11,7)") t7 = S_11("(11,6)") t8 = S_11("(11,5)") t9 = S_11("(11,4)") t10 = S_11("(11,3)") t11 = S_11("(11,2)") t12 = S_11("(11,1)") t13 = S_11("(10,7)")

 

c1*t1*t2*t3*t4*c7*t5*t6*t7*t8*t9*t10*t11*t12*t13 

Click here to view the 13 move algorithm for the Futurama permutation solution in WolframAlpha

Here are some questions posed by Dana C. Ernst:
1. Can we do better (i.e., fewer moves to fix the cycles)?
2. Under what circumstances do we not need to introduce two “clean” people?
3. Would only using one “clean” person ever be useful?
4. Could you use fewer moves if you allowed more than two “clean” people?

We now know the answer to some these questions. Students from the University of California, San Diego have improved the result, giving a better algorithm for finding the minimum number of switches to put everyone’s head back in the right places, give optimal solutions for two particular situations, and give necessary and sufficient conditions for it being possible to represent the identity permutation as $m$ distinct transpositions in $S_n$.

Here is the paper submitted on April 26, 2012.

These notes are a wonderful introduction to group theory! Though only 39 pages in length, it covers a fair amount of the subject in a very clear fashion by relating the theory to the study of the Rubik’s Cube.

A Rubik’s Cube is a $3\times3\times3$ cube in which the 26 subcubes on the outside are internally hinged in such a way that rotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sides is painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a single color after it has been randomized by repeated rotations. The puzzle was invented in the 1970s by the Hungarian Ernő Rubik and sold millions of copies worldwide over the next decade.

The number of possible positions of the Rubik’s cube is

$\frac{8!\cdot12!\cdot3^{8}\cdot2^{12}}{2\cdot3\cdot2}=43252003274489856000$

(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are $901083404981813616$ positions up to conjugacy by whole-cube symmetries.

The group of operations on the Rubik’s cube is known as Rubik’s group, and the Cayley graph of that group is called Rubik’s graph. The minimum number of turns required to solve the cube from an arbitrary starting position is equal to the graph diameter of Rubik’s graph, and is sometimes known as God’s number. While algorithms exist for solving a cube from an arbitrary initial position, they are not necessarily optimal (i.e., requiring a minimum number of turns) and computation of God’s number is very difficult. It had been known since 1995 that a lower bound on the number of moves for the solution (in the worst case) was 20, it was not known until demonstrated by Rokicki et al. (2010) that no configuration requires more than 20 moves, thus establishing that God’s number is 20.

These notes are based on a 2-week course that I taught for high school students at the Texas State Honors Summer Math Camp. All of the students in my class had taken elementary number theory at the camp, so I have assumed in these notes that readers are familiar with the integers mod n as well as the units mod n.

Because one goal of this class was a complete understanding of the Rubik’s cube, I have tried to use notation that makes discussing the Rubik’s cube as easy as possible. For example, I have chosen to use right group actions rather than left group actions.

Introduction

The goal of these notes is to give an introduction to the subject of group theory, which is a branch of the mathematical area called algebra (or sometimes abstract algebra). You probably think of algebra as addition, multiplication, solving quadratic equations, and so on. Abstract algebra deals with all of this but, as the name suggests, in a much more abstract way! Rather than looking at a specific operation (like addition) on a specific set (like the set of real numbers, or the set of integers), abstract algebra is algebra done without really specifying what the operation or set is. This may be the first math you’ve encountered in which objects other than numbers are really studied!

A secondary goal of this class is to solve the Rubik’s cube. We will both develop methods for solving the
Rubik’s cube and prove (using group theory!) that our methods always enable us to solve the cube.

References

Douglas Hofstadter wrote an excellent introduction to the Rubik’s cube in the March 1981 issue of Scientific American. There are several books about the Rubik’s cube; my favorite is Inside Rubik’s Cube and Beyond by Christoph Bandelow. David Singmaster, who developed much of the usual notation for the Rubik’s cube, also has a book called Notes on Rubik’s ’Magic Cube,’ which I have not seen.

For an introduction to group theory, I recommend Abstract Algebra by I. N. Herstein. This is a wonderful book with wonderful exercises (and if you are new to group theory, you should do lots of the exercises). If you have some familiarity with group theory and want a good reference book, I recommend Abstract Algebra by David S. Dummit and Richard M. Foote.

Topics covered are:

• Functions
• Groups
• The Rubik’s Cube and Subgroups
• Cube Notation
• Making the Rubik’ Cube into a Group
• Subgroups
• Simplifying Group Notation
• Generators
• The Symmetric Group
• Disjoint Cycle Decomposition
• Rubik’s Cube
• Group Homomorphisms
• The Sign Homomorphisms
• The Alternating Group
• Group Actions
• Valid Configurations of the Rubik’s Cube