The Prisoner of Benda and the Futurama Theorem

Dana C. Ernst
Plymouth State University
dcernst [at] plymouth [dot] edu

Gordon Mathematics Forum

Just use your arrow keys to advance the slides.



Here is short clip with the Professor Farnsworth and the Globe Trotters:

The Prisoner of Benda

The mind swap problem

Here are the swaps that take place during the episode:

The upshot: \[a \rightarrow h \rightarrow l \rightarrow p \rightarrow b \rightarrow e \rightarrow w \rightarrow a \text{ and } f \leftrightarrow z\]

The mind swap problem (continued)

The question is:

Can the machine be used to put everyone back if we aren't allowed to use the machine on the same pair of bodies more than once?

We need to use math!

In the first 25 seconds of this video, we see that the Professor, Bender, and Amy realize that they are in trouble.

Note:This video was made by SingingBanana, and if you watch the whole video, you'll get another full description of the problem and solution.

The symmetric group

We can model this problem in terms of permutations (i.e., rearrangements) of numbers. It turns out that the set of all permutations of the numbers 1 through $n$ forms a "group" under composition.

A group is a set with an associative binary operation satisfying:

The group of permutations of $\{1,2,\ldots, n\}$ is called the symmetric group and is denoted by $S_n$.

Permutation diagrams

One way of representing an element of the symmetric group is via permutation diagrams, which we illustrate by way of example.



Permutation diagrams (continued)

Let's try multiplying.


Let $\alpha$ and $\beta$ be as on previous slide. Then


But on the other hand


We see that products of permutations do not necessarily commute (order matters).

Permutation diagrams (continued)

However, sometimes permutations do commute.


Let $\beta$ and $\gamma$ be as before. Then


Notice that these result in the same diagram. So, $\beta$ and $\gamma$ commute.

Permutation diagrams (continued)

Let's do one more example.


Let $\gamma$ be as before. Then


The rightmost diagram is the identity in $S_{5}$ (it's the "do nothing action"). Since $\gamma \gamma$ is equal to the identity, $\gamma$ must be its own inverse.

Some comments

The mind swap problem as diagrams

If we let $a=1$, $h=2$, $l=3$, $p=4$, $b=5$, $e=6$, and $w=7$, $f=8$, and $z=9$, then the mind swap problem from Futurama can be depicted as:


Rephrasing the problem

The problem can be restated as:

Can we multiply a permutation by a sequence of transpositions that we haven't used yet to obtain the identity permutation?

It turns out that, in general, the answer is yes, but we need to add in two more "clean" people to pull this off.

The Futurama Theorem

Here is the solution presented in the show.


Note:This image is taken from The Infosphere: The Futurama Wiki.

Cycle notation

Before describing the solution, we need to introduce a more efficient way of encoding our permutations. One such method is called cycle notation.



Cycle notation (continued)

Let's try multiplying using cycle notation. Note: We will multiply left to right. The more common way is to do it right to left (like function composition).


Consider $\alpha, \beta, \sigma$, and $\gamma$ in $S_{5}$ as in the previous examples. Then

\[\alpha \beta=(1, 2, 3, 4, 5)(2, 4, 3)=(1, 4, 5).\]

On the other hand,

\[\beta \alpha=(2, 4, 3)(1, 2, 3, 4, 5)=(1, 2, 5).\]


Let $\beta$ and $\gamma$ be as before. Then

\[\gamma\beta =(2\ 4\ 3)(1\ 5)=(1\ 5)(2\ 4\ 3)=\beta\gamma.\]

We saw earlier that $\beta$ and $\gamma$ commute with each other.

Some more comments

Fixing a single 7-cycle

Consider just the 7-cycle $(1,2,3,4,5,6,7)$. Introduce two new bodies that have not had their minds swapped, say $x$ and $y$. To return all minds of 1-7 back to their rightful owner, multiply the cycle (on the right) by the following sequence of transpositions:


Let's verify that this actually works! First, notice that all of these transpositions are distinct and since $x$ and $y$ are new, we never used any of the transpositions to obtain our original scrambling of minds.


Note: $x$ and $y$ now have their minds swapped with each other, but they never sat in the machine at the same time!

Fixing an arbitrary $k$-cycle

Consider the $k$-cycle $(1,2,\ldots,k)$. How do we "fix" this cycle?

As before, introduce two new bodies that have not had their minds swapped, say $x$ and $y$. To fix a $k$-cycle, multiply the cycle (on the right) by the following:

\[(x,1)(y,k)(y,k-1)\cdots (y,2)(y,1)(x,k)\]

Why does this work?!

Fixing products of disjoint cycles

What do we do when we have multiple cycles to start with?

Let's try it out!

Closing remarks


Questions to ponder

Thank you!

Dana C. Ernst
Plymouth State University
dcernst [at] plymouth [dot] edu

These slides were made using deck.js and MathJax.