Futurama Theorem
Theorem
Let $A_{n - 2} \subset A_n$ be a subgroup of the alternating group on $n$ letters $A_n$.
For any element $x \in A_{n - 2}$, let $x = x_1 x_2 \dots x_k$, where $x_i \in H$ is a transposition.
Then there exists $y$ which can be represented as a series of transpositions $y_1 y_2 \dots y_j \in A_n$ such that:
- $(1): \quad y x = z$, where $z$ contains no transpositions from $H$
- $(2): \quad y_a \ne x_b$ for all $a, b$.
Proof
Let $w = (n [n - 1])$, that is, the transposition of the $n^{th}$ and $n - 1^{th}$ letters that we consider $A_n$ acting on.
Then the permutation $x^{-1} w$ is the $y$ of the theorem.
$\blacksquare$
Historical Note
This theorem was developed and proved by American comedian Kenneth Keeler for an episode of the television show Futurama titled The Prisoner of Benda [1].
In the episode, there exists a device which can switch any two peoples minds.
However, it is discovered that no two bodies can be switched more than once.
The question is asked:
- Once a switch has happened, can all the minds be returned to their proper bodies?
In the episode, it is claimed that no matter how permuted a group becomes, all minds can be returned to their proper bodies with at most two additional individuals.