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

Then .

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:

**Every permutation may be written as a composition of disjoint cycles.**

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 .

**Disjoint cycles commute.**

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.

**Futurama Theorem:**

Let be a finite set.

Then any permutation of can be reduced to the identity by joint composition with distinct transpositions where and

**Proof:**

Like the mathematician and problem solving expert George Pólya once said: if you can’t solve a problem then there is probably an easier problem which you can solve, find it.

So let’s start by considering k-cycles instead of general permutations.

Let be a k-cycle.

Then will send back to itself given that

Similarly we see that sends back to itself.

Moreover sends both and back to themselves.

Therefore continuing inductively we find that for we have:

.

Unfortunately sends and not back to itself.

To fix this we can use another auxiliary element and compose:

.

Then has the property that it fixes every and swaps .

This in turn can be corrected for by transposing at the end.

Therefore acts like the identity.

This solves the problem for k-cycles.

For example if the characters initially swap according to then the disjoint cycle form of is just the single k-cycle .

Hence will undo so that everyone is back into their own bodies, including the globetrotters .

Now for a general permutation we can use the fact that every permutation may be written as a composition of disjoint cycles. This brings us back into familiar territory, and in combination with the fact that disjoint cycles commute we can solve the general problem.

Let be a general permutation composed of disjoint cycles .

Moreover let be the permutation corresponding to s.t (as above)

Then since disjoint cycles commute

.

Thus .

Therefore to get back to the identity we compose with whenever is odd and leave like it is when is even. We can do this because we have not yet used .

This completes the argument, or to quote “Sweet” Clyde Dixon: “Q to the E to the D”.

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.

**Generalized Futurama Theorem:**

Let be a prime number and let be a finite set s.t .

Then any permutation of can be reduced to the identity by joint composition with distinct p-cycles in , not exclusively contained in , where .

**Proof:**

Like in the previous argument we first want to prove the statement for cycles, which we know are building blocks for general permutations.

Let be an m-cycle in

Then

fixes every element in .

Remaining elements are permuted among themselves, with the restriction that .

By rearranging the order of in the leftmost cycle of if necessary we may assume reduces to a p-cycle.

We have one unused element left, namely .

We may use to fix in the p-cycle resulting from to get a cycle solely in terms of .

Suppose where is some permutation of .

Define

Then one can verify that fixes and permutes in a p-cycle.

Thus is some p-cycle in .

Therefore for some since p is prime.

Now turning our attention to general permutations suppose where are disjoint cycles.

For each let be the permutation s.t for some (as above).

Since disjoint cycles commute

.

Since we have yet to use the p-tuple we may compose with

the p-cycle to turn the permutation back to the identity

(unless in which case we need to do nothing).

Below are some exercises related to this post, feel free to try them:

**Exercise 1 (The Swap Puzzle – Easy):**

Consider a puzzle where the numbers are scrambled in some way into different boxes.

The only legal move is to swap numbers between two boxes.

The puzzle is solved when the numbers are arranged from to in increasing order.

**i)** Show that the puzzle can always be solved.

**ii)** Deduce that any permutation may be written as a composition of transpositions.

**Exercise 2 (A Shorter Swapping Sequence – Intermediate):**

Suppose the Futurama characters swap according to the permutation .

The method outlined in the Futurama theorem would yield the inversion sequence

.

This requires 13 swaps and 2 extra bodies.

**i)** Show that this permuation can be brought back to the identity using only 9 swaps and *no* extra bodies.

**ii)** Find a sequence of transpositions that cannot be undone unless one uses 2 extra bodies.