Futurama theorem

This article's references may not meet Wikipedia's guidelines for reliable sources. Please help by checking whether the references meet the criteria for reliable sources. (February 2011)

The Futurama theorem is a theorem from the mathematical field of study known as group theory. It is named after the American animated science fiction TV show Futurama since it was invented purely for the episode "The Prisoner of Benda". The theorem applies to a scenario in which two individuals have used a machine to swap minds, but cannot directly swap their minds back into their own bodies because of an immune response. The theorem demonstrates that, no matter how many individuals have swapped minds with one another, everyone's mind can be returned to his or her original body by using only two additional individuals who have yet to swap minds with anyone.

The theorem was proven by the show's writer Ken Keeler, who also has a PhD in mathematics.

Contents 1 Problem description 1.1 The proof 2 An intuitive explanation for the proof 3 Swapping processes in the episode 3.1 How the minds messed up 3.2 How the minds were restored 4 See also 5 External links

[edit] Problem description

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?

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, regardless of how many people have switched minds, everyone can be returned to his or her own body by introducing only two new individuals into the chain.

[edit] The proof

The formal proof is shown in the episode for a brief moment while 'Sweet' Clyde of the Globetrotters 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:

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:

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

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:

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.

[edit] An intuitive explanation for the proof

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)

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.

[edit] Swapping processes in the episode

The following two tables show the process of how the minds became permuted and the process of how they were put back into their own bodies. Each column represents a body, each name in the headings represents the original owner of the body, and the first letter of each name is used to represent the corresponding (original) mind. Each row shows two swapped minds, and the last row shows the final status.

[edit] How the minds messed up

Professor	Leela	Hermes	Amy	Wash bucket	Nikolai	Bender	Fry	Zoidberg
P	L	H	A	W	N	B	F	Z
A			P
			B			P
L	A
			W	B
							Z	F
				N	B
	H	A
L	H	A	W	N	B	P	Z	F

[edit] How the minds were restored

Professor	Leela	Hermes	Amy	Wash bucket	Nikolai	Bender	Fry	Zoidberg	Helper 1 (Clyde)	Helper 2 (Ethan)
L	H	A	W	N	B	P	Z	F	H1	H2
							H1		Z
								H2		F
							F			H1
								Z	H2
H2									L
				H1						N
	L								H
					N					B
		H							A
						B				P
			A						W
P										H2
				W					H1
P	L	H	A	W	N	B	F	Z	H1	H2

[edit] See also

• Body swap appearances in media

[edit] External links

• The Futurama theorem explained
• The Infosphere's take on the Futurama theorem
• Futurama Theorem and Puzzle A variant of the proof and an interactive tool