Keeler’s theorem explained
I’m not usually fond of Futurama, but I’m crazy about math, and this one episode has particularly captured my mind. It goes by the name “The Prisoner of Benda”, the tenth episode in season six and features real, pretty cool math. (And not the usual crap you see on TV.)
And here’s what happens: Apparently there’s this professor, (whose name I have forgotten) who has just invented the mind-switcher, a machine which allows two users to swap minds. Everyone is totally enthusiastic and eager to have their minds swapped. (Which I don’t quite understand, because I would have been horrified.) In the end, there’s a huge mess with people (and robots) in wrong bodies and to make it worse, it happens that the machine cannot swap back two minds if they’ve already swapped once. So, can we bring everybody back in their own body? And how?
“I’m not sure. I’m afraid we need to use… math!” –Professor Farnsworth
It turns out, you’ll need two extra people to sort out the problem. The solution to this is widely known as Keeler’s Theorem, discovered and proven from one of the writers of the show, Ken Keeler, who has earned a Ph.D. in applied mathematics in Harvard before becoming a writer.
Normally, this proof isn’t worthy of the title “theorem”, but I guess popular culture doesn’t mind a bit flashiness.
Elementary combinatorics
Photo: It’s a Lottery by MarkyBon – CC
This is a post on elementary combinatorics, frequently used in probability theory. Basically that just means, we’ll be counting without actually counting. Or counting sophistically. Whatever you prefer.
Some enumerative problems can be solved through urn models, i.e. the number of possibilities to draw a fixed number of balls from an urn. After this post we can solve the following (classical) problems:
Problem 1: How probable is it that at least two people in a group of $m$ people have their birthday on the same day of year?
Problem 2: How probable is it that you get exactly $r$ correct numbers in a lottery?
You can (hopefully) solve these problems in the end (as an excercise).
A matches game puzzle
Photo: aftermat(c)h by ankaatje – CC
This nifty little puzzle comes from an excercise sheet of our algorithms and data structures course at the university. Our task was to find a winning formula for a game and prove it.
Imagine 100 matches laying on the table. Alice and Bob take at most 10 matches from the table in turn. They can choose how many matches they want to take, but they have to take at least one match. Whoever gets the last match, wins the game. Suppose Alice starts, how should she play to win the game every time?
You should really try to solve this puzzle on your own before reading my explanation after the jump.
