We all know this feeling: someone’s in your seat, and now you’re the nutcase who’s going to take someone else’s seat. After all that what’s the probability the last person on the plane will be able to sit in the correct seat?
The three number trick is just a simple version of this one (but here it is quicker and simpler).
In which we confess further delight in arithmetic…
1) Send us your candidates for an interesting fact about the number 2012; the winner will receive a handsome Math Prize! As mentioned on the podcast, already its larger prime factor, 503, has a neat connection to the primes 2,3,5, and 7.
2) So what is it about the tetrahedral numbers, and choosing things? In particular, why is the Nth tetrahedral number (aka the total number of gifts on the Nth day of Christmas) is exactly the same as the number of ways of choosing 3 objects out of (N+2)? Not hard, really, to prove, but can you find a simple or intuitive explanation?
3) Finally, about those M&M’s. Maybe I exaggerated a little bit when I claimed this problem holds all the secrets of the thermodynamics of the universe, but I don’t see how! Many classic equations, such as Newton’s Law of Cooling or the Heat Equation, the laws of thermodynamics, and fancier things as well, can all be illustrated by shuffling red and blue M&M’s around. What I don’t understand is how anything got done before M&M’s were invented!
The world’s largest ever exhibit of Escher’s works is on display, right now, at the Boca Raton Musuem of Art If you can, this is a must see event! We talk with the collector, Rock J. Walker about his fascination with this amazing work.
And of course we answer last week’s puzzle, and hear from listeners!
We said during the most recent podcast that we’d offer the answer to the ending puzzle on the website.
Twitter user @snoble posted a hint on #mathfactor that points to the right answer.
First, I’ll review the problem. You and nine other prisoners will be lined up in the morning front to back. Each of you will have either a blue or red hat placed upon your head. Each person can see all the hats on the heads of people in front of him, but not the color of his own or of any of the people behind.
The guards will then proceed to the rear of the line and ask that person the color of the hat on his own head. He must guess and if he guesses wrong, sadly, he’ll be shot. Either way, the guard then proceeds to the number nine position and repeats through all of the other prisoners.
Knowing that this will happen and with a night to plan, what strategy can the prisoners develop to maximize their expected survival rate?
During the show, I suggested a 75% solution and claimed that you can do much better. In fact, 95% of the prisoners should survive. Here’s how it is done.
The person in the rear of the line announces the “red” if he sees an even number of red hats in front of him and “blue” if the number is odd. He’ll be right about his own hat 50% of the time. There’s no help for that as he has no information at all. But from this, all future prisoners know with certainty the color of their own hat! Here’s how:
If the person in the rear says “red,” number nine knows that he saw an even number of red hats. If he also sees an even number of red hats, he knows that his own hat must be blue. Likewise, if he sees an odd number of hats, the only way for ten to have seen an even number of red hats is if his own hat is read.
By keeping track of each answer and the change between even / odd indicated by the answers, each person can correctly guess the color of his own hat for a total of 95% success.
Interestingly, this works even if the guards know what the prisoners are up to. Unlike the hat problem in GB where the hat placers can make failure 100% likely knowing the strategy by cheating and placing hats of all the same colors on the heads of the players, in this setup, the strategy works not only on random placement but also on malicious placement.
The hint offered on twitter was to think about “parity.” When hiring computer programmers I would sometimes offer this as an interview questions and often the people who got it would answer me with this one word and we’d move on. It refers to parity bits in some communication protocols on computers. When you send information over the wire, the signal may occasionally be distorted. Parity bits are an approach to self-correction. Suppose you send through a block of 1024 bits, 1’s and 0’s. Suppose that you use 1023 for data and in the last bit, called a parity bit, you send 1 of the there are an even number of 1’s in the other bits, and 0 otherwise. The receiving party can then check to make sure that this works out. If a bit got flipped, you can request re-transmission of that block. Of course, two errors might give you a false positive here, but if you know about how often errors occur, you can choose the size of the block you send such that errors occur as rarely as you like (with an increased cost of transmission because of parity bits.)