The Futurama Theorem and Puzzle
With a widely acknowledged success of the CBS series Numb3rs that ran for five years (January 23, 2005, March 12, 2010), it is no longer a question whether mathematics is a valid subject for movies. The appearance of mathematics in the movies, though, has a reasonably long history. Oliver Knill of Harvard University has put together an admirable collection of movie clips that one way or another relate to mathematics.
Yet there appears to be a unique event of creating and proving a real math theorem in support of an episode in an animated TV series. In the episode "The Prisoner of Benda" of the animated science fiction TV show Futurama, two characters create a mind-switching device, which can swap the minds of any two individuals. And the mind swaps do takes place. One shortcoming of the process is that a mind swap is not repeatable; immune system defences block a repeated swap. One questino arises rather naturally: Is it possible - under the circumstances - to return the minds to their original bodies? If yes, how?
A theorem has been stated and proven by the show's writer Ken Keeler, that affirms the possibility of the desired "backward" exchange. To perform the feat, the theorem requires two "clean" individuals who have not swapped the minds previously (at least not with anybody who now aspire to get their mind back.) The theorem became known as the Futurama Theorem.
To formulate the theorem I refer to the notions of permutation, cycle, and transposition. Every permutation is representable as a product of disjoint cycles. Using this property, the proof of the theorem reduces to separately treating individual cycles.
I denote the cycle of elements a b c ... f as (a b c ... e f), meaning that the cycle is the permutation that takes a to b, b to c, ..., e to f, and f to a. A transposition is a 2-element cycle. (Note that, in these notations, it does not matter which of the elements comes first.) The product of two permutations p and q is a permutation t that is obtained by first applying p and then q:
(The interpetation of the cycle (a b c ... e f) is that each element of the cycle carries the mind of the preceding element.)
Lemma 1
(a b c ... e f)(a b) = (a c ... e f)(b), where (b) is a 1-element cycle, i.e., a fixed point.
Thus a transpositions of two elements adjacent in a cycle removes one of them (both of them in a 2-element cycle) from the cycle. In terms of the Futurama episode, such a transposition leaves b with its own mind.
The process can be repeated with additional transpositions of adjacent elements, leading in the end to a product of 1-elemnt cycles. It is noteworthy that the transpositions obtained in the process are all distinct because each contains an element not available for the forthcoming transpositions.
Lemma 2
For an element x, different from any of a, b, c, ..., e, f,
(a b c ... e f)(a x) = (a x b c ... e f).
Lemma 2 shows how to insert a new element into an existing cycle. Lemma 1 then shows that by a sequence of unique transpositions can be reduced to
Lemma 3
(a x y b)(x b) = (a x)(b y).
All three lemmas can be verified directly. The applet below is an interactive tool that may help gain insight into the mechanism outlined in the three lemmas.
Futurama Theorem
Let A be a finite set, with more than 1 element; x, y ∉ A. Any permutation π of A can be converted to a trivial (identity) permutation with a sequence of products by transpositions each of which includes just one of x, y.
Proof
First split π into the product of disjoint cycles. Since disjoint cycles commute, the transpositions in question will be applied separately to each individual cycle of length greater than 1. Using Lemma 2, insert x and y anywhere into a given cycle. If necessary, use Lemma 1, to reduce the cycle to a 4-cycle of the form
(In the applet below, click on two circles whose values you want swapped.)
What if applet does not run? |
Permutations
- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations
- The Futurama Theorem and Puzzle
- A Shuttle Puzzle
|Activities| |Contact| |Front page| |Contents| |Games|
Copyright © 1996-2018 Alexander Bogomolny
71999921