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.
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)."