Posts Tagged ‘math.IT’

Hat Guessing Puzzles, The Revenge

September 20, 2007

    I guess since my previous hat color guessing problem was so popular, I might as well talk about the other one I know.  However, this one isn’t meant to attack the foundations of mathematics.  The problem is as follows:

Three people are sitting in a circle.  Black or white hats (50% chance of each) will all be placed on their heads, and they will be able to see everyone’s hat color but their own.  They will all simultaneously write down on a piece of paper either “Black”, “White”, or “Pass”, trying to guess their own hat color.  All the people collectively win (whatever that means) if at least someone guesses their hat correctly and no one guesses incorrectly.  They lose if anyone guesses incorrectly, or everyone passes.  If they can agree on a strategy beforehand, what is their best chance of winning?

    Again, there is the problem that no information can be conveyed to someone about their own hat color, so they would seem to be guessing blindly (talking and facial expressions are prohibited).  However, they can still win 75% of the time.  Figure it out!

    Once you solve the easy version of this puzzle, the harder version is with larger numbers of people.  As a partial spoiler, stick to 2^n-1, where the best win rate is 2^n-1 out of 2^n.  How is this possible?  (Answer below the fold)

(more…)