Hat Hints
Some hints to follow up on the seven-intern version of the red-hat blue-hat puzzle from the last post. The case where there are seven interns is much trickier than the case where there are only three interns, but once you see the solution to seven, you can see the solution for all 2n-1 interns. For numbers of interns that do not line up with powers of two like this, the optimal solution is an open problem (though, using Dominic's construction, you can always use the 2n-1 solution as a lower bound).
So here is the hint. You don't know the seven interns' strategy, but day after day you observe them getting free tiramisu (about 7/8 of the time), and here is what you notice:
- The interns have apparently worked out a geeky way to distinguish each other, because each shows up at the cafe wearing a name tag with a number from 001 to 111, that is, the numbers one through seven in binary.
- You notice that, when all seven interns get hats of the same color, they all guess wrong. Sometimes they all guess wrong with other color combinations too.
- But very strikingly, most days, only one intern guesses. And when only one intern guesses, the guess is always right. The most entertaining days are when only one intern has a hat of a different color. Inevitably the other interns stay quiet and that intern guesses his own hat color correctly.
Yesterday the interns did not get tiramisu. The first three got red hats and the rest got blue hats, and they all guessed their hat color. They were all wrong.
Today, the first four interns got red hats and the last three got blue hats. Intern #4 was the only one to submit a guess and, as happens whenever only one intern guesses, she guessed "red" correctly.
What the heck are they doing, and how often can they get tiramisu doing this?
Tomorrow we will give red hats to interns #3 and #7. Which intern will correctly guess that her hat is "blue" tomorrow?
Posted by David at May 25, 2007 11:46 AM