I am a mad scientist, and I have invented a machine that will switch the minds of two people into each other's bodies.

Being mad, though, my machine has one fatal drawback: once two bodies have used the machine, then the machine will never work again on that particular pair of bodies (regardless of whose minds are inhabiting them currently).

Here's an example. Bodies A and B use the machine, so person a is in Body B, and person b is in Body A.

Body   A B C
person b a c

Next, suppose Bodies A and C switch, so person c is in Body A, and person b is in Body C.

Body   A B C
person c a b

Finally, B and C switch, so person a is in body C, and person b is back in Body B.

Body   A B C
person c b a

Unfortunately, bodies A and C have already gone through the machine, so the machine will not work on that pair again. Therefore, if we want to restore everyone to his original body, at least one more additional body is needed for temporary storage.

Question 1:
At the beginning, once bodies A and B switch, can they ever switch back, leaving all others in their rightful bodies when all is said and done? If so, how many total bodies would need to be involved (including A and B)?

Question 2:
Suppose n people continue to switch bodies with other members of their group (again, each pair of bodies can only use the machine once). How many total bodies, in terms of n, would need to be involved to sort everyone out?

Suppose A and B switch. They can switch back with 4 people.

Posted by Math Man on 2012-08-02 10:40:58