There are two excellent reasons to be watching Futurama on Comedy Central. Most important, it’s a darn funny show. A close second, it’s chock full of math. Indeed, there is an entire website by Dr. Sarah Greenwald devoted to the myriad math references on the show. Many of the writers on the show have a background in math, physics, computer science, etc. and there are all sorts of sly math references snuck in for those who pay attention. From Dr. Greenwald’s website:
For example, Ken Keeler, who has a Ph.D. in applied mathematics from Harvard University, discussed his transition from mathematics to comedy writing during a tight job market in an interview with gotfuturama.com. When he was asked whether his education paid off, he responded: “Well, sure. For example, Bender’s serial number is 1729, a historically significant integer to mathematicians everywhere; that “joke” alone is worth six years of grad school, I’d say.”
But apparently Ken Keeler and company can’t stick to just the known math world. In the most recent episode, “The Prisoner of Benda,” Dr. Keeler proved a new theorem for the show.
The question is simple enough. If you have a machine which can switch the bodies of two people but you are only allowed to use the machine once per pair, then once you’ve mixed a group of people, how many extra people do you need to get everyone back into their original bodies? (Who says math isn’t practical?)
For example, if Dr. Özaydin and Dr. Breen were to switch bodies, then they aren’t allowed to switch back directly. But Dr. Özaydin could swap with Dr. Remling so that he’s in Dr. Remling’s body, and then swap with Dr. Breen and return to his original body. Which leaves Dr. Remling in Dr. Breen’s body and vice versa. But those bodies have already done a swap, so they’re stuck unless some else comes to help out (paging Dr. Wei!).
Since we are asking about rearranging a group of, say, n people, this is a question in terms of math about the symmetric group on n objects. That is the group of all permutations of n objects. The question is then, if is a permutation on n objects, then how many more objects do we have to add to our list of permutable objects in order be able to go from to the identity element of the symmetric group (i.e. the initial, unpermuted arrangement of the objects) using only transpositions (aka swaps) without using the same transposition twice?
The answer? Two.
And here’s the proof (click on the picture for a closeup):
For details on the episode, the theorem, and it’s application to restoring everyone to their rightful bodies, there is a summary here.
This is so cool, we even forgive David X. Cohen (the show’s Executive Producer and head writer) for first announcing it in an interview with the American Physical Society. Just so long as the American Mathematical Society gets the next exclusive!
I’m afraid we need to use… math!