May 25, 2007
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:
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
|Copyright 2007 © David Bau. All Rights Reserved.|