I was watching a re-run of an episode of Futurama last night, and problem is presented. The professor stares into the camera and declares "This can only be solved with MATH!"

Here's the problem (from wiki)


The theorem is modeled in the episode by the following problem: In the show, Amy and Professor Farnsworth have created a mind-switching device, which can swap the minds of any two individuals. After a brief discussion, they decide to swap their own brains. They then discover that once two people have switched minds once, they can never switch back, due to the brain’s natural immune response. This raises a question: once two people have swapped minds, can they get back to their original bodies by means of a third party? Bender eagerly switches minds with Amy at this point.

Throughout the rest of the episode, mind swapping occurs quite frequently. Amy (as the professor) swaps with Leela, Fry swaps with Dr. Zoidberg, Nikolai (the playboy ruler of the Robo-Hungarian empire) swaps with a bucket, and so on. In the end it is discovered by ‘Sweet’ Clyde Dixon that by including no more than two new people in this mind swap game, everyone can always return to their original body.

I tried to figure it out on my own...but quickly realized it well beyond me. With a little google-fu, I discovered that one of the writers for the show has a PhD. in Mathmatics and actually created a new theorem just for this show. I thought that was kind of cool.

Here's the theorem if you want to check it out.
The formal proof is shown in the episode for a brief moment while 'sweet' Clyde of the "globe trouders" manages to prove the theorem. The proof is as follows:

First let π be some k-cycle on [n] = {1 ... n} WLOG [without loss of generality] write:

π = 1 2 ... k k+1 ... n
2 3 ... 1 k+1 ... n

Let <a,b> represent the transposition that switches the contents of a and b. By hypothesis π is generated by DISTINCT switches on [n]. Introduce two "new bodies" {x,y} and write

π* = 1 2 ... k k+1 ... n x y
2 3 ... 1 k+1 ... n x y

For any i=1 ... k-1 let σ be the (l-to-r) series of switches

σ = (<x,1> <x,2> ... <x,i>) (<y,i+1> <y,i+2> ... <y,k>) (<x,i+1>) (<y,1>)

Note each switch exchanges an element of [n] with one of {x,y} so they are all distinct from the switches within [n] that generated π and also from <x,y>. By routine verification

π* σ = 1 2 ... n x y
1 2 ... n y x

i. e. σ reverts the k-cycle and leaves x and y switched (without performing <x,y>).

NOW let π be an ARBITRARY permutation on [n]. It consists of disjoint (nontrivial) cycles and each can be inverted as above in sequence after which x and y can be switched if necessary via <x,y>, as was desired.

http://en.wikipedia.org/wiki/Futurama_theorem#The_proof

The entire length of my PhD I had has my desktop a screen grab of Prof Farnsworth's blackboard during the lecture where he 'proved' the neutrino tastes of gravy. While I can't say I'd have been able to do it myself I'm surprised such a theorem wasn't already known, the structure of permutation groups is a popular area in group theory. Actually a guy I work with did his PhD in that so I might ask him this tomorrow :p (/edit Or rather Monday, today being Friday!)

How would you phrase the theorem in a textbook or paper?

"Every non-trivial element of the S_n subgroup of S_{n+2} has a non trivial inverse in S_{n+2} which may be factored into unique transpositions not part of S_n ?"

"Every element of the S_n subgroup of S_{n+2} may be factored into zero or more unique tranpositions which are not part of S_n."

"If G is a symmetric group, and H is a symmetric subgroup of G, and degree(G) >= 2 + degree(H) then for every element, h, of H there exists a finite sequence of unique elements of G - H where the product equals h."

The entire length of my PhD I had has my desktop a screen grab of Prof Farnsworth's blackboard during the lecture where he 'proved' the neutrino tastes of gravy.

The mathematics of wanton burrito meals?
heh, maybe if I one day do a PhD it will be on superdupersymmetric string theory.


I'm also surprised such a theorem didn't already exist. The proof itself is not difficult and looks like it could be one of those "optional" questions at the end of a first year abstract algebra problem set.

It does make me happy that a "Futurama Theorem" exists though.