Irreversible body swap

Question

In Futurama's episode 6x10, the professor invents a device which allows to switch mind between two bodies. He then switches his mind with Amy. It later turns out that the a given pair of bodies can not complete this procedure twice with each other.

In this situation, is it possible to undo what is done using other bodies to swap minds between?

What if initially not 2, but N minds has been switched between N bodies? Consider the worst case scenario that each pair of N bodies has been switched already.

For example, if they use 1 additional body:
Let the Professor be $P$ and Amy be $E$. Upper case letters represent a body, lower case letters - minds. They start out with $Pp,Ee$ then after one switch, they have $Pe, Ep$. If they use third person $A$, then they can do $Pe, Ea, Ap$ and $Pp, Ea, Ae$, but $E$ and $A$ has already switched once so they would face the same problem again.

Answer 1

A more detailed plot summary of "Prisoner of Benda" reveals that reversal for the worst-case swappage of $N$ bodies is possible with only two additional bodies for any $N$. The proof of this is a non-trivial exercise in group theory.

According to several sources, the writing of this episode marks the first known instance of a group theorem being devised and proven specifically for the sake of a TV program plotline. According to Wiki, the theorem even has a name, "Keeler's Theorem", after the mathematician who devised and proved it

Answer 2

I think you need 2 buddies A and B:
1. switch Emmy with A, Prof with B,
2. switch Emmy with B, Prof with A,
3. switch A and B.

For N "scrambled" people, N is an upper bound.

For the lower bound, it depends in what sequence the people got swiched. For example if A switched with B and C with D, you can undo the mixup with A<->C, B<->D, A<->D, B<->C.

I think it can alwasy be done with 4 extra buddies. I'll show it by example:

If you keep only people "out of their mind" the general configuration is that of a permutation, i.e. a number of cycles: A has B's mind, B has C's mind ... E has A's mind. Let's write Ab for A has B's mind. For example, we could have the configuration with three cycles:

Ab Bc Cd De Ea | Fg Gh Hi If | Jk Kl Lm Mj

Comes first buddy X (Xx) and switches mind with A, B, C in order, the minds are now arranged as:

Ax Bb Cc Dd Ee | Fa Gg Hh Ii | Jf Kk Ll Mm | Xj

Most people are now OK, except for the first in each loop, and X. The remaining people to fix are:

Ax Fa Jf Xj

You can see the remaining people now form a loop (X dragged one mind over to the next loop). To fix that, a new buddy Y comes in and exchanges minds with X, J, F, A (from the end). The minds now are like this:

Aa Ff Jj Xy Yx

Now we are back in the case of Emmy and Prof. Unfortunately X and Y already have switched minds, so 2 more buddies are necessary to switch these minds back.

This is just an example, but I believe it works regardless of the number of cycles. And nobody in the original group needs to swap minds. One shortcut is when there is a single cycle. Then you can jump directly to Y for the final cycle. But it also works with X.

For 3 people, you still have the upper bound of 3 additional buddies. Or you can see that 3 people are always a cycle, so you can fix it Y and the 2 last buddies.

PS: I didn't see there is a better answer already.