For those of you who don’t know Futurama, it is an animated sci-fi sitcom that have been running regularly on TV.
In one particular episode “The Prisoner of Benda” (s06e10) a character named Professor Farnsworth builds a mind swapping machine (or body swapping machine depending on how you look at it) which operates on two users at a time.
The characters in the show all find they have their personal reasons for wanting to swap bodies with one another. So not long after finding out about the machine they start engaging in a body swapping extravaganza.
Professor Farnsworth switches body with Amy, Amy switches with Leela and Fry switches with Zoidberg etc…
They however soon realize that the machine only works one way.
Once two bodies have been swapped, the same two bodies cannot be swapped back.
The characters eventually start regretting their decision and wish to swap back into their own bodies, but how?
In the words of Professor Farnsworth(now in Benders robot body):
“I’m not sure. I’m afraid we need to use………………MATH” *evil look*.
Unexpectedly by the end, the two super intelligent basketball globetrotters, Ethan “Bubblegum” Tate and “Sweet” Clyde Dixon come to rescue and mathematically prove it can be done using two extra bodies.
So what was their solution and how did they prove it?
This theorem if you will, was constructed exclusively for this episode by Ken Keeler (who by the way holds a PhD in applied mathematics from Harvard University, but instead chose a lucrative career as a story writer…).
The problem clearly revolves around permutations, so to understand the strategy most effectively let’s frame the problem in that language.
I briefly wrote something about permutations in a previous post but I’ll make a more detailed overview for this problem.
If you’re already familiar with permutations, you may skip directly to the theorem.
Otherwise you may benefit from reading on.
Formally a permutation of a set is bijection .
Normally however we don’t care about how the set elements are labelled, and simply take where .
For example if
then we could relabel as since it is only the way in which the elements are permuted that matters not the labels themselves.
A permutation cycle is usually denoted
meaning and .
There are two special kinds of cycles:
If then we say fixes .
If then we call a transposition (i.e a “swap”)
The identity permutation (usually denoted ) is the permutation that fixes every element of the set.
Clearly in the problem a series of transpositions have taken place.
Our task is to find transpositions different from the ones already applied to turn the overall permutation back to the identity i.e so that everyone is back into their own body.
Permutations can be composed just like ordinary functions (although algebraists usually like to write composition from right to left in what is called Reverse Polish Notation we will write them from left to right like most of you are probably more familiar with).
Composition is perhaps best illustrated via an example:
Suppose we have two cycles
To arrive at this one simply looks at what does to each number.
For example starting with we see that and .
Therefore after which the procedure is repeated for .
You notice that when we eventually get to we are mapped back to which is where we started, so this completes a cycle. One moreover sees that is a fixed by even though neither nor fixes . Also note that if a permutation fixes an element we usually don’t write it out, which is why was omitted on the right hand side.
There are a few useful facts about permutations that I won’t prove here but are fundamental to the study of permutations:
Two cycles are disjoint if they move (i.e don’t fix) no point in common.
(The proof essentially goes by strong induction on the number of points moved by the permutation)
In the example above we saw how the permutation was put
into disjoint cycle form .
This means whenever are disjoint.
The result should be obvious if you think about it.
For example but partly
because on left hand side whereas on right hand side.
Ok, now that we have plowed through all that language, let’s put it to good use.
Playing around with the same idea I actually found one can generalize this statement to machines that swap p-tuples of bodies in a cyclic shift with p prime, disallowing the same p-tuple to ever swap again (in any order), using at most p extra bodies.
Below are some exercises related to this post, feel free to try them: