The Futurama Problem

Futurama

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…

The_Prisoner_of_Benda

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”.

     

    The_Prisoner_of_Benda_Globetrotters
     

    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.

    GeneralizedFuturama

    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.

    SwapPuzzle

    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.

    Advertisements
    This entry was posted in Algebra, Combinatorics, Uncategorized and tagged , , , , , , , , , . Bookmark the permalink.

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s