## The Futurama Problem

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 $\Omega$ is bijection $\sigma:\Omega \rightarrow \Omega$.
Normally however we don’t care about how the set elements are labelled, and simply take $\{ 1,...,n \}$ where $n = |\Omega|$.
For example if $\Omega = \{ Professor\;Farnsworth,Fry,Leela,Zoidberg,Bender,Amy,Hermes\}$
then we could relabel $\Omega$ as $\{1,...,7\}$ since it is only the way in which the elements are permuted that matters not the labels themselves.

A permutation cycle is usually denoted $\sigma = (a_1\;a_2\;...\;a_k)$
meaning $\sigma\; a_i = a_{i+1} \; \forall i < k$ and $\sigma\; a_k = a_1$.

There are two special kinds of cycles:
If $k=1$ then we say $\sigma$ fixes $a_1$.
If $k=2$ then we call $\sigma = (a_1\;a_2)$ a transposition (i.e a “swap”)

The identity permutation (usually denoted $\iota$) 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 $\sigma_1 = (1\;3\;5\;2),\; \sigma_2 = (3\;1\;5\;6\;2)$
Then $\sigma_1\sigma_2 = (1\;3\;5\;2)(3\;1\;5\;6\;2) = (1\;2\;5\;6)(3) = (1\;2\;5\;6)$.
To arrive at this one simply looks at what $\sigma_1\sigma_2$ does to each number.
For example starting with $1$ we see that $\sigma_2\;1 = 5$ and $\sigma_1\;5 = 2$.
Therefore $\sigma_1\sigma_2\;1 = 2$ after which the procedure is repeated for $2$.
You notice that when we eventually get to $6$ we are mapped back to $1$ which is where we started, so this completes a cycle. One moreover sees that $3$ is a fixed by $\sigma_1\sigma_2$ even though neither $\sigma_1$ nor $\sigma_2$ fixes $3$. Also note that if a permutation fixes an element we usually don’t write it out, which is why $3$ 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 $\sigma_1\sigma_2 = (1\;3\;5\;2)(3\;1\;5\;6\;2)$ was put
into disjoint cycle form $(1\;2\;5\;6)(3)$.
• Disjoint cycles commute.
This means $\sigma_1\sigma_2 = \sigma_2\sigma_1$ whenever $\sigma_1,\;\sigma_2$ are disjoint.
The result should be obvious if you think about it.
For example $(1\;2\;3)(4\;5) = (4\;5)(1\;2\;3)$ but $(1\;2\;3)(3\;4) \neq (3\;4)(1\;2\;3)$ partly
because $2 \rightarrow 3$ on left hand side whereas $2 \rightarrow 4$ on right hand side.
•

Ok, now that we have plowed through all that language, let’s put it to good use.

Futurama Theorem:

Let $\Omega$ be a finite set.

Then any permutation $\sigma$ of $\Omega$ can be reduced to the identity by joint composition with distinct transpositions $(a\;b)$ where $a \in \Omega \cup \{ x,y \},\; b \in \{ x,y \}$ and $x,y \notin \Omega$

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 $\sigma = (a_1\;...\;a_k)$ be a k-cycle.
Then $\tau = (a_1\;x)(a_2\;x)\sigma$ will send $a_1$ back to itself given that $\tau\;a_1 = (a_1\;x)(a_2\;x)\sigma\; a_1 = (a_1\;x)(a_2\;x)\; a_2 = (a_1\;x)\; x = a_1$
Similarly we see that $\tau = (a_2\;x)(a_3\;x)\sigma$ sends $a_2$ back to itself.
Moreover $(a_1\;x)(a_2\;x)(a_3\;x)\sigma$ sends both $a_1$ and $a_2$ back to themselves.

Therefore continuing inductively we find that for $\tau := (a_1\;x)...(a_1\;a_k)\sigma$ we have:
$\tau\;a = a\;\;\; \forall a \in \{ a_1,...,a_{k-1}\}$.

Unfortunately $\tau$ sends $a_k \rightarrow x$ and not back to itself.
To fix this we can use another auxiliary element $y$ and compose:
$\tau^* := (a_k\;y)(a_1\;x)...(a_k\;x)(a_1\;y)\sigma$.

Then $\tau^*$ has the property that it fixes every $a \in \{a_1,...,a_k\}$ and swaps $x,y$.
This in turn can be corrected for by transposing $(x\;y)$ at the end.

Therefore $(x\;y)(a_k\;y)(a_1\;x)...(a_k\;x)(a_1\;y)\sigma$ acts like the identity.

This solves the problem for k-cycles.
For example if the characters initially swap according to $\sigma = (1\;2)(2\;3)(3\;4)...(k-1\;k)$ then the disjoint cycle form of $\sigma$ is just the single k-cycle $(1\;2...k)$.
Hence $(x\;y)(k\;y)(1\;x)...(k\;x)(1\;y)$ will undo $\sigma$ so that everyone is back into their own bodies, including the globetrotters $x,y$.

Now for a general permutation $\sigma$ 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 $\sigma = C_1 C_2...C_n$ be a general permutation composed of disjoint cycles $C_i$.
Moreover let $\sigma^*_i$ be the permutation corresponding to $C_i$ s.t $\sigma^*_i C_i = (x\;y)$ (as above)

Then since disjoint cycles commute
$\sigma^*_1...\sigma^*_n\sigma = \sigma^*_1...\sigma^*_n C_1 ... C_n = \sigma^*_1 C_1...\sigma^*_n C_n = (x\;y) ... (x\;y) = (x\;y)^n$.

Thus $\sigma^*_1 ...\sigma^*_n \sigma = \begin{cases} \iota, & if\;\; n\;even \\ (x\;y) & if\;\;n\;odd \end{cases}$.

Therefore to get back to the identity we compose $\sigma^*_1 ... \sigma^*_n\sigma$ with $(x\;y)$ whenever $n$ is odd and leave like it is when $n$ is even. We can do this because we have not yet used $(x\;y)$.

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 $p \geq 3$ be a prime number and let $\Omega$ be a finite set s.t $|\Omega| \geq p$.

Then any permutation $\sigma$ of $\Omega$ can be reduced to the identity by joint composition with distinct p-cycles in $\Omega \bigcup \{x_1,...,x_p\}$, not exclusively contained in $\Omega$, where $\Omega \bigcap \{x_1,...,x_p\} = \emptyset$.

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 $\sigma = (a_1\;...\;a_m)$ be an m-cycle in $\Omega$

Then
$\tau := (a_m\;a_{m-1}\;x_{p-2}\;...\;x_1)...(a_2\;a_1\;x_{p-2}\;...\;x_1)(a_1\;x_{p-1}\;x_{p-2}\;...\;x_1)\sigma$
fixes every element in $\{a_1,...a_{m-1}\}$.

Remaining elements $a_m,x_1,...,x_{p-1}$ are permuted among themselves, with the restriction that $a_m \rightarrow x_{p-1}$.
By rearranging the order of $x_{p-2},...,x_1$ in the leftmost cycle of $\tau$ if necessary we may assume $\tau$ reduces to a p-cycle.

We have one unused element left, namely $x_p$.
We may use $x_p$ to fix $a_m$ in the p-cycle resulting from $\tau$ to get a cycle solely in terms of $x_1,...,x_p$.

Suppose $\tau = (a_m\;x_{p-1}\;y_{p-2}\;...\;y_1)$ where $y_{p-2},...,y_1$ is some permutation of $x_{p-2},...,x_1$.

Define $\sigma^* := (x_p\;a_m\;y_{p-2}\;y_{p-3}\;...\;y_1)(x_{p-1}\;x_p\;a_m\;y_{p-3}\;...\;y_1)\tau$

Then one can verify that $\sigma^*$ fixes $a_m$ and permutes $x_p,x_{p-1},y_{p-2},...,y_1$ in a p-cycle.

Thus $\sigma^*$ is some p-cycle in $x_1,...,x_p$.
Therefore $\sigma^* = (x_1\;...\;x_p)^j$ for some $j \in \mathbb{Z}$ since p is prime.

Now turning our attention to general permutations $\sigma$ suppose $\sigma = C_1 C_2...C_n$ where $C_1,...,C_n$ are disjoint cycles.

For each $C_i$ let $\sigma^*_i$ be the permutation s.t $\sigma^*_i C_i = (x_1\;...\;x_p)^{j_i}$ for some $j_i \in \mathbb{Z}$ (as above).

Since disjoint cycles commute
$\sigma^*_1...\sigma^*_n\sigma = \sigma^*_1...\sigma^*_n C_1 C_2...C_n = \sigma^*_1 C_1 \sigma^*_2 C_2 ... \sigma^*_n C_n =$
$(x_1\;...\;x_p)^{j_1}...(x_1\;...\;x_p)^{j_n} = (x_1\;...\;x_p)^{\sum_{i=1}^n j_i} = (x_1\;...\;x_p)^{(\sum_{i=1}^n j_i)\; (mod\;p)}$.

Since we have yet to use the p-tuple $[x_1,...,x_p]$ we may compose $\sigma^*_1...\sigma^*_n\sigma$ with
the p-cycle $(x_1\;...\;x_p)^{-(\sum_{i=1}^n j_i)\; (mod\;p)}$ to turn the permutation back to the identity
(unless $\sum_{i=1}^n j_i \equiv 0\;(mod\;p)$ 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 $\{ 1,...,n \}$ are scrambled in some way into $n$ different boxes.
The only legal move is to swap numbers between two boxes.
The puzzle is solved when the numbers are arranged from $1$ to $n$ 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 $(4\;5)(8\;9)(1\;2)(3\;9)(6\;5)(3\;7)(3\;6) = (1\;2)(3\;4\;5\;6\;7\;8\;9)$.

The method outlined in the Futurama theorem would yield the inversion sequence
$(2\;y)(1\;x)(2\;x)(1\;y)(9\;y)(3\;x)(4\;x)(5\;x)(6\;x)(7\;x)(8\;x)(9\;x)(3\;y)$.

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.