So can someone with more math knowledge comment on how "Brand New" this theorem is? Comparing the Geekosystem post with the tone of the original APS article, it sure feels like a certain amount of breathless hyperbole was added to the former...

The article isn't very accurate. In the episode, two people can swap minds, but the same two minds cannot be swapped twice. The article says that "after enough swaps everyone can find their original body." But this is incorrect. The actual math problem solved says that by adding two people to the pool (the harlem globetrotters in the episode) you can then always find a way for everyone to swap into their original bodies.

The math proof shows this by starting with an arbitrary permutation of minds (pi) for n people, then adds two new people x and y to show that there now exists another permutation of minds (sigma) that "undoes" the original permutation. This means there's a way for everyone to get their bodies back.

Without the addition of two people x and y there is no such guarantee.

To understand the details you'll need to know about group theory. Specifically permutations. This isn't a "deep" problem. But it is awesome that it's correct and on TV!

>To understand the details you'll need to know about group theory.

I wrote up an algorithm to swap the minds back, and then proved its correctness, and its running time. It might be more understandable than the group theory proof. It's in a comment thread on reddit: http://www.reddit.com/r/math/comments/d3ar3/tonights_futuram...

Not really "brand new" at all. It wouldn't be out of place in the first week of an Algebra course.

You don't really need much math background to understand the proof. At the top, where he writes pi = (top line of numbers, bottom line of numbers), he means the permutation that sends the first element to the second place, the second element to the third place, and so on.

If you think about it, every permutation can be split into cycles of this form (a -> b, b-> c, c->d, ..., e->a). One of these cycles, that's of length K, is called a "K-Cycle".

I think that's the only terminology you need to follow the proof.