Loading...

Futurama and Keeler's Theorem: Original Edit

254,513 views

Loading...

Loading...

Transcript

The interactive transcript could not be loaded.

Loading...

Loading...

Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Aug 22, 2010

Futurama is the property of 20th Century Fox, and Comedy Central. Clips in this video fall under fair use for review, commentary and educational use. The Prisoner of Benda first aired on the 19th of August 2010.

For more information on this episode see http://theinfosphere.org/The_Prisoner...

For a screenshot of the theorem see http://pool.theinfosphere.org/images/...

For an improvement to Keeler's Theorem by mathematicians from the University of California, see this paper http://arxiv.org/pdf/1204.6086.pdf

For more information on the maths of Futurama see http://mathsci.appstate.edu/~sjg/futu...

Click here for my introduction to Group Theory http://www.youtube.com/watch?v=ylAXYq...

Let Fry, Zoidberg, the Professor, Washbucket, Hermes, Bender, Leela, the Emperor, and Amy be the initial set of people swapping minds. Then the various swapping of bodies gives the permutation \pi where
\pi = (ap)(ab)(pl)(aw)(fz)(ew)(hl) = (fz)(ahlpbew)

By Keeler's Inversion Theorem we can return the swapees to their original bodies by introducing two new people, namely Sweet Clyde and Bubblegum Tate, and swapping bodies via the permutation \sigma, where;
\sigma = (fs)(zt)(zs)(ft)(ps)(wt)(ls)(et)(hs)(bt)(as)(pt)(ws)
and \pi . \sigma = 1. This is a total of 13 body swaps to return people back to normal.

In this case we can reduce the total number of body swaps to 9, and exclude the addition of two extra people, by letting \sigma be a different permutation, namely;
\sigma = (pf)(wz)(lf)(ez)(hf)(bz)(af)(pz)(wf), where \pi . \sigma = 1 as required.

Ron Evans of the University of California has answered my question about whether the problem could be solved in fewer than 9 moves. Ron writes:
"Note that 9 swaps (transpositions) is best possible in this case. To see this, write (1234567)(89) as a product P of t transpositions, none equal to (89), and assume for the purpose of contradiction that t less than 9. Let B denote the rightmost factor of P containing one of the entries 8,9; without loss of generality, B=(18) (otherwise cyclically reorder the entries 1,2,3,4,5,6,7 and/or 8,9). We can move B to the far right in P by interchanging B with disjoint factors and/or repeatedly using formulas of the form (18)(1c)=(c8)(18) with c less than 8. Thus (123456789)=(1234567)(89)(18) can be written as a product of t-1 less than 8 transpositions. This is a contradiction, since a 9-cycle cannot be expressed as a product of fewer than 8 transpositions (see Lemma 1(a) of http://arxiv.org/pdf/1204.6086.pdf)."

Loading...

When autoplay is enabled, a suggested video will automatically play next.

Up next


to add this to Watch Later

Add to

Loading playlists...