I’ve recently been re-watching Futurama (the entire series is available to Amazon Prime subscribers).
In the episode “The Prisoner of Benda” (original air date: 19th August 2010) the Professor and Amy build a machine that allows them to swap minds (so Amy’s mind is in the Professor’s body, and the Professor’s mind is in Amy’s body). However when they try to switch their minds back they discover that the machine will not operate twice using the same pair of bodies. However the Professor (still in Amy’s body) suggests that they might be able to swap back using a third body as temporary storage space.
Bender volunteers and swaps his mind into Amy’s body (and so the Professor’s mind is swapped into Bender’s body). The Professor (in Bender’s body) realises that if the Bender and Professor bodies now swap minds (which is permitted), then the Professor’s mind ends up inside his own body, but Bender and Amy still have swapped minds and the Bender and Amy bodies have already used the machine, so they cannot use it to swap back. Amy (in the Professor’s body) then asks: “Is it possible to get everyone back to normal using four or more bodies”. The Professor (in Bender’s body) replies: “I’m not sure. I’m afraid we need to use … (dramatic pause) … math!”[s].
In the meantime, and for various sub-plot reasons, a fair amount of mind/body swapping goes on. The following is a complete list of the bodies involved in the swaps:
Amy ↔ Professor
Amy ↔ Bender
Leela ↔ Professor
Amy ↔ Washbucket
Fry ↔ Zoidberg
Emperor ↔ Washbucket
Hermes ↔ Leela
If we denote the body of B contains the mind of M as BM, then we can show the sequence of swaps as:
start: (AA) (PP)
A↔P: AP PA (BB)
A↔B: AB PA BP (LL)
L↔P: AB PL BP LA (WW)
A↔W: AW PL BP LA WB (FF) (ZZ)
F↔Z: AW PL BP LA WB FZ ZF (EE)
E↔W: AW PL BP LA WE FZ ZF EB (HH)
H↔L: AW PL BP LH WE FZ ZF EB HA
At this point in the story, two of the Harlem Globetrotters (Ethan “Bubblegum” Tate and “Sweet” Clyde Dixon) prove mathematically that no matter how many swaps have taken place, everyone can be returned to normal with the addition of two extra players (answering Amy’s question from earlier). And they proceed to perform thirteen swaps, using the Globetrotters as the extra players to restore everyone to normal.
This has become known as the Futurama Theorem, and is believed to be the first (and onliest) mathematical proof created specifically to further the plot of a TV show.
The proof is constructive, and operates as follows:
We can form the subjects into a collection of cycles where the minds need to follow the arrows to be restored. For example, the situation we have consists of two cycles:
FZ → ZF [→ FZ] (2-cycle)
AW → WE → EB → BP → PL → LH → HA [→ AW] (7-cycle)
With the addition of two extra players, X and Y, we can use them to transfer the minds along the cycles. We don’t need to know which combinations have already been used because we are going to use X or Y in every swap, and they have not been involved in any of the cycles.
So for the 2-cycle, we use X and Y to take the wrong minds from F and Z and replace them with the right minds:
start: FZ ZF | XX YY
F↔X: FX ZF | XZ YY
Y↔Z: FX ZY | XZ YF
F↔Y: FF ZY | XZ YX
X↔Z: FF ZZ | XY YX
X and Y end up swapped, but we don’t need to resolve them until the end. In sorting out the other players X and Y only ever interact with the other players and not each other, so they can always swap at the end (if necessary).
For the 7-cycle, we can use X to transfer the minds down the line until we get down to the final two, at which point we bring Y into play to avoid having to use the first two bodies again:
start: AW WE EB BP PL LH HA | XY YX
A↔X: AY WE EB BP PL LH HA | XW YX
W↔X: AY WW EB BP PL LH HA | XE YX
E↔X: AY WW EE BP PL LH HA | XB YX
B↔X: AY WW EE BB PL LH HA | XP YX
P↔X: AY WW EE BB PP LH HA | XL YX
L↔X: AY WW EE BB PP LL HA | XH YX
H↔Y: AY WW EE BB PP LL HX | XH YA
A↔Y: AA WW EE BB PP LL HX | XH YY
H↔X: AA WW EE BB PP LL HH | XX YY
And X and Y have ended up restored anyway, so we don’t need to sort them out.
So for any permutation we can break it into cycles and sort out the cycles individually using X and Y, and then swap X and Y at the end (if necessary).
The method uses (k + 2) swaps to resolve each k-cycle, and then maybe an extra 1 at the end to sort out X and Y (if required – which it is if there are an odd number of cycles).
So in this case we use 4 + 9 = 13 extra swaps and 2 extra people to resolve the situation.
The following questions remain to be answered:
(1) Could Amy, the Professor, Bender, Leela, Washbucket, Fry, Zoidberg, the Emperor and Hermes have got themselves restored to normal with fewer than 2 extra players? If so what is the minimum number of extra players required?
(2) Could they have got themselves back to normal in fewer than 13 extra swaps? If so what is the minimum number of swaps required?