Math hangout: brainswap mayhem

Recently on a social network, Dana Ernst pointed out something called the “futurama theorem”: the characters all swap their brains and need to prove a theorem before they can swap back. It sounded cute, so I made it the topic of a hangout discussion.

Of course, it would normally be very easy to swap back, just retrace your steps, but the show introduced a (silly of course) technical hurdle: once a pair of bodies have had their brains swapped, they can never have their brains swapped again. (The reason they give has something to do with the body’s immune system rejecting a second swap.)

This hurdle is quite serious: the only way for two people who have swapped their brains to ever get back to normal is to bring some new people into the story! So initially, we must ask:

Suppose that a group $A_1,\ldots,A_n$ of people have had their brains mixed up in some fashion. Can we bring in some number new people $B_1,\ldots,B_m$ (who are “clean” in the sense that they never swapped) and use them to restore $A_1,\ldots,A_n$ to their original brains?

The answer is “yes”; in fact it is not hard to see that $n$ clean people will suffice. You simply dump all of the brains in bodies $A_1,\ldots,A_n$ into the bodies of $B_1,\ldots,B_n$, and then put them back one by one into the correct place. (Of course, if some $A_7$ already had his correct brain, then you actually don’t move him at all, or else you could never put him back this way!) This unfortunately has the adverse effect of leaving $B_1,\ldots,B_n$ all messed up, but this is no problem, because they have never swapped with each other before and so they can simply swap amongst themselves.

The sharper question now becomes:

How few clean people can we get away with?

We quickly saw that just one clean person $B$ is not enough, even if there is only one swapped pair $A_1$ and $A_2$. Indeed, in this case there are only two moves available: swap $B$ with the first body, and swap $B$ with the second body. But if you try applying these moves in either order you will see that they don’t get you back to normal!

Now, in the case of just one swapped pair, we already know that two clean people $B_1$ and $B_2$ is enough. So the next interesting case is to decide whether two clean people is enough to restore three permuted people. To do this, we needed to introduce some notation. Suppose that $A_1,A_2,A_3$, have permuted so that $A_2$ is in $A_1$’s body, $A_3$ is in $A_2$’s body, and $A_1$ is in $A_3$’s body. We will denote this by \[A_2A_3A_1\] In other words, the bodies are the positions and the symbols $A_1$ and $A_2$ are the brains, so to say that $A_2$ is in the first position is to say that the brain of $A_2$ is in the first body, and so on.

Now, if clean people $B_1$ and $B_2$ come along, let us say their bodies are in the fourth and fifth positions, so we write \[A_2A_3A_1B_1B_2\] Then the solution looks like this:
\[B_1A_3A_1A_2B_2\] \[B_1B_2A_1A_2A_3\] \[B_1A_2A_1B_2A_3\] \[B_1A_2A_3B_2A_1\] \[A_1A_2A_3B_2B_1\]
Yay, we did it! Of course $B_1$ and $B_2$ are now swapped, but that’s no problem because they can always just swap back.

Next, we found out that a similar strategy using just two clean people $B_1$ and $B_2$ works for an arbitrary “cycle”, that is, any conundrum of the form $A_2A_3\cdots A_nA_1$. The argument we gave was very ad-hoc in style, so I will not attempt to describe it in this post. We simply saw a pattern and convinced ourselves rigorously that it must work for any such cycle. Then we ran out of time!

---

Afterward

First, the argument that we gave can be expressed in a much more compact way if you use traditional permutation notation from group theory. This is what you will find if you search for “futurama theorem” and read the first results. Perhaps a more detailed discussion would have led us to “discover” this notation out of a need to express our arguments.

And second, we did not have time to address arbitrary (non-cyclic) permutations. In fact, we were almost done since any permutation can be decomposed into a product of disjoint cycles. If we had more time, this would have been an awesome opportunity to “discover” this beautiful fact.