Hats, Hats, And Hats Some More

Time for a new problem I suppose. This one is going to be a bit weird, because as I understand it part of this is actually an open problem. The solution is only known in a few special cases, and so part of the problem will be to find how those cases fit in. Here we go:
There are N people in a room, each of them wearing hats. The hats can either be white or black, and standard hat rules will apply. At a specified time, each person simultaneously must either guess their own hat colour or pass. The players win the game if nobody guessed their hat colour incorrectly and somebody guessed correctly. They lose the game if either somebody was wrong, or everybody passed. The players are free to strategize before the hats are assigned. Find a strategy for the N player case such that in the limit as N goes to infinity, the probability of success goes to 1.

This problem as it is stated can be solved, its not an open problem really. Solving it in the N person case optimally is an open problem, so don't worry about that.

3 comments:

Anonymous said...

Wait, so there is an infinite pool of hats (white and black) which are placed on the heads of people. They all simultaneously either guess or pass, presumably based on a strategy agreed before ahead of time, who's input is the hats everyone sees.

So no information at all can be gleaned from the other hats due to the hat pool being infinite. Why are they even in a room together?

Strategy, regardless of N, Bill guesses randomly his hat color. Everyone who's !Bill passes. 50-50.

-!Bob

kstevens said...

Your first paragraph is totally correct. Your second one raises a good question, but hasn't basically every single hat problem I've presented been about getting a surprising amount of information out of seemingly nothing?

That strategy is a good first attempt at the problem, however, in the limit as N goes to infinity the probability of success does not go to 1, so you haven't solved it yet.

Anonymous said...

Oh.... I think I kind of figured out the shape of it. I can think of a way to win 75% of the time for any number of people greater than 2.