Futurama Theorem

From ProofWiki
Jump to navigation Jump to search

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.