# Difference between revisions of "Futurama theorem"

(→External links) |
(→Proof: put into better mathematical notation, and spelled out the step from a single cycle to an arbitrary permutation in more detail. Also, the proof is improved by fixing a single σ, rather than describing a family of σ which work.) |
||

Line 47: | Line 47: | ||

It is also not necessary for Clyde and Bubblegum (or Fry and Zoidberg) to take turns so often in the machine; it is only convenient for the presentation. | It is also not necessary for Clyde and Bubblegum (or Fry and Zoidberg) to take turns so often in the machine; it is only convenient for the presentation. | ||

− | == Proof == | + | == Mathematical Proof == |

[[file:The Mind-Switcher.jpg|right|thumb|225px|The [[Mind-Switcher]] and its inventors.]] | [[file:The Mind-Switcher.jpg|right|thumb|225px|The [[Mind-Switcher]] and its inventors.]] | ||

− | + | A mathematical statement of the theorem is that for any permutation π of n elements, there is a permutation σ of the original elements and 2 new elements such that σ inverts π and σ is a product of distinct transpositions, each of which includes at least one of the 2 new elements. | |

− | |||

− | |||

− | + | First, we suppose that the permutation π is a cycle of length k ≤ n. Without loss of generality, we can assume that the original elements are {1 ... n}, and π is the permutation (written in cycle notation) <1...k>. Let the new elements be x and y, and let σ be the permutation | |

− | + | <center>σ = <ky><1x><2x>...<kx><(k-1)x><1y>.</center> | |

− | + | Note that σ consists of k transpositions between x and one of the cycle elements, and 2 transpositions between y and one of the cycle elements. We will call σ the canceling permutation for π, because | |

− | + | <center>σπ = <ky><1x><2x>...<kx><(k-1)x><1y><1...k> = <xy>.</center> | |

− | + | This shows how a single cycle can be undone, with an additional transposition between x and y. | |

− | + | Now, let π be an arbitrary permutation, which we can write as a product of disjoint cycles as π=π<sub>1</sub>...π<sub>m</sub>. Let σ<sub>1</sub>,...,σ<sub>m</sub> be the canceling permutations for π<sub>1</sub>,...,π<sub>m</sub>, and let σ be either σ<sub>1</sub>...σ<sub>m</sub> (if m is even) or <xy>σ<sub>1</sub>...σ<sub>m</sub> (if m is odd). Since the cycles π<sub>1</sub>,...,π<sub>m</sub> are disjoint, σ<sub>i</sub> and π<sub>j</sub> commute, for i ≠ j. Therefore we have | |

− | + | <center>σπ = <xy><sup>m</sup>σ<sub>1</sub>...σ<sub>m</sub>π<sub>1</sub>...π<sub>m</sub> = <xy><sup>m</sup>σ<sub>1</sub>π<sub>1</sub>...σ<sub>m</sub>π<sub>m</sub> = <xy><sup>2m</sup> = id.</center> | |

− | + | This shows how an arbitrary permutation π can be undone. | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Solution algorithm in plain English == | == Solution algorithm in plain English == |

## Revision as of 17:31, 19 May 2013

The **Futurama theorem** is a real-life mathematical theorem invented by *Futurama* writer Ken Keeler, who holds a PhD in applied mathematics, purely for use in the Season 6 episode "The Prisoner of Benda".

It is the first known theorem to be created for the sole purpose of entertainment in a TV show, and, according to Keeler, was included to popularize math among young people.

The theorem proves that regardless of how many mind switches between two bodies have been made, they can still all be restored to their original bodies using only two extra people, provided these two people have not had any mind switches prior.

## Contents

## Background

In the episode "The Prisoner of Benda", Professor Farnsworth and Amy create a mind-switching machine, only to afterwards realise that when two people have switched minds, they can never switch back with each other. Throughout the episode, the Professor and the Globetrotters try to find a way to solve the problem using two or more additional bodies, and, in the end, the solution is shown both in action and on the board.

## Inversion

Keeler uses the method outlined in the proof to restore all minds to their respective bodies. Here are his transpositions. He uses thirteen switches total:

- Sweet Clyde's body (receiving Dr Zoidberg's mind) ↔ Fry's body (receiving Sweet Clyde's mind)
- Bubblegum Tate's body (receiving Fry's mind) ↔ Dr Zoidberg's body (receiving Bubblegum Tate's mind)
- Sweet Clyde's body (receiving Bubblegum Tate's mind) ↔ Dr Zoidberg's body (receiving Dr Zoidberg's mind)
- Bubblegum Tate's body (receiving Sweet Clyde's mind) ↔ Fry's body (receiving Fry's mind)
- Sweet Clyde's body (receiving Leela's mind) ↔ Professor Farnsworth's body (receiving Bubblegum Tate's mind)
- Bubblegum Tate's body (receiving Emperor Nikolai's mind) ↔ Washbucket's body (receiving Sweet Clyde's mind)
- Sweet Clyde's body (receiving Hermes's mind) ↔ Leela's body (receiving Leela's mind)
- Bubblegum Tate's body (receiving Bender's mind) ↔ Emperor Nikolai's body (receiving Emperor Nikolai's mind)
- Sweet Clyde's body (receiving Amy's mind) ↔ Hermes's body (receiving Hermes's mind)
- Bubblegum Tate's body (receiving Professor Farnsworth's mind) ↔ Bender's body (receiving Bender's mind)
- Sweet Clyde's body (receiving Washbucket's mind) ↔ Amy's body (receiving Amy's mind)
- Bubblegum Tate's body (receiving Bubblegum Tate's mind) ↔ Professor Farnsworth's body (receiving Professor Farnsworth's mind)
- Sweet Clyde's body (receiving Sweet Clyde's mind) ↔ Washbucket's body (receiving Washbucket's mind)

However, this is not the fewest number of switches possible in this scenario. Because Fry and Zoidberg only switched with each other and no one else, and there is an odd number (1) of other switched groups of bodies, they could have been used as the two spare bodies, completing the restoration in only nine switches:

- Fry's body (receiving Leela's mind) ↔ Professor Farnsworth's body (receiving Zoidberg's mind)
- Zoidberg's body (receiving Emperor Nikolai's mind) ↔ Washbucket's body (receiving Fry's mind)
- Fry's body (receiving Hermes's mind) ↔ Leela's body (receiving Leela's mind)
- Zoidberg's body (receiving Bender's mind) ↔ Emperor Nikolai's body (receiving Emperor Nikolai's mind)
- Fry's body (receiving Amy's mind) ↔ Hermes's body (receiving Hermes's mind)
- Zoidberg's body (receiving Professor Farnsworth's mind) ↔ Bender's body (receiving Bender's mind)
- Fry's body (receiving Washbucket's mind) ↔ Amy's body (receiving Amy's mind)
- Zoidberg's body (receiving Zoidberg's mind) ↔ Professor Farnsworth's body (receiving Professor Farnsworth's mind)
- Fry's body (receiving Fry's mind) ↔ Washbucket's body (receiving Washbucket's mind)

Had there been an even number of distinct switched groups, Fry's mind and Zoidberg's mind would have ended up back in the opposite bodies, and having already switched, they could not be switched back without two spare bodies. The solution given in the theorem works for all scenarios.

It is also not necessary for Clyde and Bubblegum (or Fry and Zoidberg) to take turns so often in the machine; it is only convenient for the presentation.

## Mathematical Proof

A mathematical statement of the theorem is that for any permutation π of n elements, there is a permutation σ of the original elements and 2 new elements such that σ inverts π and σ is a product of distinct transpositions, each of which includes at least one of the 2 new elements.

First, we suppose that the permutation π is a cycle of length k ≤ n. Without loss of generality, we can assume that the original elements are {1 ... n}, and π is the permutation (written in cycle notation) <1...k>. Let the new elements be x and y, and let σ be the permutation

Note that σ consists of k transpositions between x and one of the cycle elements, and 2 transpositions between y and one of the cycle elements. We will call σ the canceling permutation for π, because

This shows how a single cycle can be undone, with an additional transposition between x and y.

Now, let π be an arbitrary permutation, which we can write as a product of disjoint cycles as π=π_{1}...π_{m}. Let σ_{1},...,σ_{m} be the canceling permutations for π_{1},...,π_{m}, and let σ be either σ_{1}...σ_{m} (if m is even) or <xy>σ_{1}...σ_{m} (if m is odd). Since the cycles π_{1},...,π_{m} are disjoint, σ_{i} and π_{j} commute, for i ≠ j. Therefore we have

^{m}σ

_{1}...σ

_{m}π

_{1}...π

_{m}= <xy>

^{m}σ

_{1}π

_{1}...σ

_{m}π

_{m}= <xy>

^{2m}= id.

This shows how an arbitrary permutation π can be undone.

## Solution algorithm in plain English

Step 1: Have everybody who's messed up arrange themselves in circles, each facing the body their mind should land in (e.g., if Fry's mind is in Zoidberg's body, then the Zoidberg body should face the Fry body).

Step 2: Go get two "fresh" (as of yet never mind-swapped) people. Let's call them Helper A and Helper B.

Step 3: Fix the circles one by one as follows:

3.0) Start each time with Helper A and Helper B's minds in either their own or each other's bodies

3.1) Pick any circle of messed-up people you like and unwrap it into a line with whoever you like at the front

3.2) Swap the mind at the front of the line into Helper A's body

3.3) From back to front, have everybody in the line swap minds with Helper B's body in turn. (This moves each mind in the line, apart from the front one, forward into the right body)

3.4) Swap the mind in Helper A's body back where it belongs, into the body at the back of the line. Now the circle/line has been completely fixed. The one side effect is that for each time a circle is fixed, the Helpers' minds will switch places, but that's OK, see below

Step 4: At the very end, after all the circles have been fixed, mind-swap the two Helpers if necessary (i.e., in case there was originally an odd number of messed-up circles)

Note: This is not the exact algorithm used in the show. This algorithm sets i = 1 in the proof provided by the show, whereas you could actually set i to be any number from 1 to k. This algorithm also reverses the order of the final two switches in the provided proof. Explained simply, the provided proof's exact method for fixing any circle is this: Helper A could switch in turn back-to-front starting and stopping at any points in the circle, then Helper B would switch back-to-front through the remainder of the circle, Helper A would then switch with the first member of Helper B's arc, and Helper B would then switch with the first member of Helper A's arc.