## May 16, 2007

This puzzle has been making the rounds.

Three Google interns go to the cafe, and a hat of a random color (equally likely red or blue) is placed on each of their heads. Nobody can see their own hat, but each can see the hats of their two friends.

For the group to get free tiramisu, each must write down a guess for their own hat color (writing "I don't know" is fine), and the team must make no wrong guesses and produce at least one correct guess. The thing is, once the interns have their random hats, no communication whatsoever is allowed.

The interns discuss this game for a minute before being hatted, and they play in a way that allows them to get free food well over 50% of the time, without any cheating.

What did they do?

And if no intern can possibly have any idea what their own hat color is, where the heck did this better-than-nothing information come from? (Perhaps this is a good way to pretend you know something when you don't?)

Posted by David at May 16, 2007 10:13 AM

This is a trick question--as they're Google interns, they can get free food 100% of the time. Joking aside, the chance of all interns having the same colored hat are 2*0.5^3, or 25% of the time; as there are three interns, if they don't all have the same color hat, two must have the same color, which is 0.5^2+0.5 = 75% of the time. So the strategy is this: If you look at your cohorts and see two different colored hats, you write "I don't know." If you look at your cohorts and see the same color, you submit the opposite color as your guess. The interns will get free tiramisu three times out of four. If the distribution of hats is not independent--if the hats are drawn from the same barrell that starts with an even number of red and blue hats--the effect is even more pronounced.

Posted by: Dominic Cooney at May 17, 2007 12:11 AM

Very good, no doubt you love your free chocolatey desserts.

What is the tiramisu-maximizing strategy for a cohort of interns (n > 3) who all cannot see their own hats?

Posted by: David at May 17, 2007 04:16 PM

Shooting from the hip:

vote(redCount>blueCount ? BLUE
: blueCount>redCount ? RED : DUNNO)

Posted by: Jacek Ambroziak at May 17, 2007 10:23 PM

Consider Jacek's strategy when there are seven friends. If five or more have the same color hat, then you get no tiramisu, but if hat colors are split three and four, then you do.

This means you get tiramisu 35/64 of the time, which is not as well as you were previously doing with 3 interns.

Is it possible to do better with seven than with 3?

Posted by: David at May 18, 2007 11:52 AM

With the obvious observation that you can always do as well as three interns with n interns (n>3) by electing three interns to be "it", conducting the strategy as for three interns, and having the rest submit "dunno." You just need to recruit n-3 less proactive interns.

Posted by: Dominic Cooney at May 24, 2007 08:39 AM

Hey, what about if the situation is :-

3 men are lined up in a row, facing front towards the same direction. There are 4 hats randomly placed on their head. 1 hat was hidden, the balance of 3 hats are black and white. All of them are not allow to speak or move. The man who has the different colour hat need to shout out his hat color to win the game.

The 1st man in line is unable to see both men. The 2nd man in the middle can only see the front hat, whereas the last person in line can see both of their hat color.

After 30 seconds, the 2nd man shouted loudly "WHITE". He won the game. Why??

Posted by: Jo at August 7, 2008 02:22 PM