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?

Good news everyone! There is an easy way to answer the first question.

Instead of X and Y we can use F and Z as additional players to resolve the 7-cycle. Using the algorithm given in the proof this resolves the 7-cycle in 9 swaps. It also swaps the minds that were occupying F and Z at the start (and without using the transition F↔Z), so the 2-cycle is resolved as a by-product of resolving the 7-cycle.

Everyone ends up restored to normal in 9 swaps, and with no additional players required:

Solution:(1) No extra players are required.But, can we do better than 9 swaps?

The following Python program attempts to resolve the situation using an increasing number of swaps until it finds a sequence of permissible swaps.

It shows there are no ways to resolve the situation in fewer than 9 swaps. It executes in 29.3s.

Run:[ @repl.it ]Solution:(2) The minimum number of swaps required is 9.We can also use the program to investigate the other situations that crop up:

The first confirms that Amy and the Professor cannot resolve their situation using only Bender as temporary storage.

The second confirms that with two extra players Amy and the Professor can resolve their situation (in 5 swaps).

The third shows that the 7-cycle can be resolved using only 6 swaps and no extra players.

And the last one is a solution to the complete puzzle.