How the heck? A puzzle with a very surprising answer

A few weeks ago I posted a puzzle about two mathematicians guessing the results of coin tosses. Dwight asked me about generalizations to more than two mathematicians. While the problem may seem very different on the surface, in my opinion the underlying issue is actually quite similar and the changes are necessary to generalize from two mathematicians to N.

I posted one version a while ago here which I will repeat as a warmup for the harder version 🙂

16 mathematicians are in a room. They are each assigned a hat, either black or white. Each hat is assigned totally independently of all the other hats and has a 50% chance of being either color. Each mathematician can see everyone else’s hat but not his/her own hat. The mathematicians all have to independently and simultaneously guess the color of their own hat. They have an hour before the hats are assigned to make a plan, then one minute to view the hats, then they each go into a voting booth to vote for the color of their own hat. While they are viewing the hats they can not communicate or signal in any manner to the other mathematicians.

The success or failure of the mathematicians is judged as a team: if every single one guesses their own hat color correctly, the team wins. If even a single mathematician guesses incorrectly, the team loses. What are the odds of their success, and what strategy should they employ to achieve it? [Hint: the odds are much better than you might first think they are. Really. If you are sure you can’t improve them I am happy to find a jurisdiction where we can play this for high stakes!]

Second version (if you thought the first version was too easy):

Everything is just like the first version, except that when the mathematicians enter the voting booth they can vote “White”, “Black”, or “Don’t know”. If anyone is wrong, they all lose. If everyone passes, they all lose. If at least one mathematician chooses a color and all mathematicians who choose colors are correct, they win. Again, what are the odds of their success, and what strategy should they employ to achieve it? Again, you can do better than you might first think!

— Max

10 comments so far

  1. Dwight Merriman (@dmerr) on

    must they vote simultaneously

  2. Satvik Beri on

    I posted on Hacker News-I’m getting 50% for both. Is there a way to get >50% in the second situation?

  3. Brian Park on

    Generalizing the strategy from the first version, I get odds of 2/3 for this one. Is it possible to get better odds than this?

  4. P Viney on

    Any one who can see an even number of whites vote. They vote themselves whatever they see the least of. They win 39202 times out of 65536, or approx 59.8% of the time.

    • Max Schireson on

      Interesting. You’ve gotten over 50% but you can do quite a bit better!

      — Max

      • Alden G on

        I like the problems you post overall, this is a very interesting one, my dad showed me this one a long time ago. I’m actually learning about algebraic coding theory right now, which has some relation to this problem.

  5. martin Schoenert on

    Is the probability 15/16?
    Is one mathematician just tagged along?
    Or can that be improved upon?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: