In true Aperiodical fashion, we left 13 days before recording another Aperiodcast, so here’s what we think about the last almost-two-weeks on the site.
We talked about:
Podcast: Play in new window | Download
Subscribe: RSS | List of episodes
The “Futurama theorem”, also known as Keeler’s Theorem after its creator, was a bit of maths invented for the Futurama episode The Prisoner of Benda, to solve a problem where the characters get their heads mixed up and need to swap them back without any one pair swapping heads twice. It was enthusiastically reported by the geeky press, and rightly so, because it’s a fun bit of real maths with a wonderful application. Dana Ernst has written some very good slides about the theorem, working from “what is a permutation?” up to the algorithm itself.
Anyway, some students from the University of California, San Diego have extended the result, giving a better algorithm for finding the minimum number of switches to put everyone’s head back in the right places, give optimal solutions for two particular situations, and give necessary and sufficient conditions for it being possible to represent the identity permutation as $m$ distinct transpositions in $S_n$.
Paper: http://arxiv.org/abs/1204.6086
via James Grime
