On Tuesday, November 6, 2012 I gave a talk titled “The Futurama Theorem and some refinements” in the NAU Department of Mathematics and Statistics Colloquium. This was the fourth time that I’ve given a talk about the Futurama Theorem (also known as Keeler’s Theorem).
The Futurama Theorem is a theorem about the symmetric group that was developed for and proved in the episode “The Prisoner of Benda” for the TV show Futurama. The theorem was proved by show writer Ken Keeler, who has a PhD in applied mathematics from Harvard. During the episode, Professor Farnsworth and Amy invent a mind swapping machine and after swapping minds, they realize that the machine cannot be used on the same pair of bodies again. After several characters swap minds, they are confronted with the problem of putting everyone’s mind back where it belongs. The Futurama Theorem proves that regardless of how many mind swaps have been made, all minds can be restored to their original bodies using only two extra people.
As with my previous talks about the Futurama Theorem, I utilized deck.js to create HTML slides and I used MathJax to typeset all of mathematical notation. One advantage of this approach is that it allows you to view the slides directly in your web browser. You can view the slides by going here. To advance the slides, just use your arrow keys. Also, you can get an overview of the slides by typing “m” or go to a specific slide by typing “g”.
This most recent talk about the Futurama Theorem was very similar to previous versions. However, I did add a few new slides. In particular, I included a summary of some recent results by Evans, Huang, and Nguyen (University of California, San Diego) that provides some refinements of Keeler’s theorem. Their paper will appear in the American Mathematical Monthly, but you can also find it on the arXiv. Here is the abstract for the paper:
An episode of Futurama features a two-body mind-switching machine which will not work more than once on the same pair of bodies. After the Futurama community engages in a mind-switching spree, the question is asked, “Can the switching be undone so as to restore all minds to their original bodies?” Ken Keeler found an algorithm that undoes any mind-scrambling permutation with the aid of two “outsiders.” We refine Keeler’s result by providing a more efficient algorithm that uses the smallest possible number of switches. We also present best possible algorithms for undoing two natural sequences of switches, each sequence effecting a cyclic mind-scrambling permutation in the symmetric group $S_n$. Finally, we give necessary and sufficient conditions on $m$ and $n$ for the identity permutation to be expressible as a product of m distinct transpositions in $S_n$.
If you are interested in comparing, you can find the slides for my previous talks about the Futurama Theorem by following the links below:
A couple hours before my talk, one of my colleagues asked if I minded if his son watched my talk via Skype. I suggested we try a Google+ Hangout and open it to anyone that was interested in watching. Having never done this before, I wasn’t exactly sure how it would work out. I sent out a quick announcement about the Hangout via G+, Twitter, and Facebook. The plan was to record the Hangout using Hangouts on Air, but we couldn’t get this set up in time. It looks like 13 people stopped by the Hangout, but it appears some of them were random Hangout lurkers. Also, it looks like there was an issue with the audio that we didn’t know about until the end.
The feedback that I received after the talk was that it went well, but I felt like I wasn’t at my best. The video camera made me more nervous than I anticipated, and trying to remember to stand where the video could see me was distracting. In addition, the light from the projector felt like a furnace.
Anyway, the Hangout was a cool experience and next time I’ll plan things out a little better. For example, as Vincent Knight suggested, instead of hosting a public Hangout, it would be better to have a G+ Circle of people that are interested in viewing and just open the Hangout to them. Thanks to Richard Green, Hugh Denoncourt, Luis Guzman and Barbara Boschmans Beaudrie for stopping by the Hangout.
Mathematics & Teaching
Northern Arizona University
MAT 123: First Year Seminar
MAT 136: Calculus I
MAT 526: Combinatorics
This website was created using GitHub Pages and Jekyll together with Twitter Bootstrap.
Unless stated otherwise, content on this site is licensed under a Creative Commons Attribution-Share Alike 4.0 International License.
The views expressed on this site are my own and are not necessarily shared by my employer Northern Arizona University.
The source code is on GitHub.
Flagstaff and NAU sit at the base of the San Francisco Peaks, on homelands sacred to Native Americans throughout the region. The Peaks, which includes Humphreys Peak (12,633 feet), the highest point in Arizona, have religious significance to several Native American tribes. In particular, the Peaks form the Diné (Navajo) sacred mountain of the west, called Dook'o'oosłííd, which means "the summit that never melts". The Hopi name for the Peaks is Nuva'tukya'ovi, which translates to "place-of-snow-on-the-very-top". The land in the area surrounding Flagstaff is the ancestral homeland of the Hopi, Ndee/Nnēē (Western Apache), Yavapai, A:shiwi (Zuni Pueblo), and Diné (Navajo). We honor their past, present, and future generations, who have lived here for millennia and will forever call this place home.