Another hat problem

Question

A finite number of prisoners, after being given their hats (black or white), are able to see one another but themselves, and then they are ordered to jot down their guess on the color of their own hat. The ones who guess right will be released. The question is: what's the most efficient strategy and how many of them can escape by using that?

It's all that's given. So this is a rather generalized version of the story and by no means can I make it more specific. Haven't found a way to begin, though. Any ideas?

Answer 1

They can ask each other. The question doesn't say anything to the contrary.

Obviously then it won't be interesting or mathematical.

So, let's say that they are not allowed verbal or non-verbal communication among themselves.

If there's no further information, and if this is a game that's played just once, then the strategy is based on strength in numbers.

If each of them tosses a coin (say black for heads and white for tails) to guess the color of his/her hat, then over a large enough sample, one would expect about 50% of them to get out. This is our baseline scenario.

But there's a better way.

They should count the total number of hats of each color, and guess that their hat is the same color as the majority. It's not a coin toss.

Let's take an example.

Let's say there are 100 prisoners. You are one of them. You can see everyone's hat but yours.

You see 70 black hats, 29 white ones.

This means that if you are wearing a black hat it is one of 71, i.e. your probability of getting a black hat is 71/100.

If you are wearing a white hat then it is one of 30, i.e. your probability of getting a white hat is 30/100.

You should guess your hat is black.

If all prisoners apply this strategy then all those wearing majority-colored hats can get out. (in our case either 70 or 71 as the case may be..which is much better than 50)

Now, let's say the number of prisoners is odd (say 101), and the visible hats are evenly distributed (50 black, 50 white), then you could choose either (or toss a coin) and end up no worse than you would if you were to indiscriminately toss a coin.

Answer 2

I will show that you can always save $\lfloor n/2 \rfloor$ persons. Let $n$ be the number of person. Have the people pair up in teams, that I will call $A_k$ and $B_k$ for $1\leq k\leq \lfloor n/2\rfloor$. $A_k$ will say his hat is of $B_k$'s color, and $B_k$ will say his hat is of $A_k$'s complement color. This way, if a pair have the same color, $A_k$ survives, and if they have different color, $B_k$ will.

This is optimal, because it yields an expected number of person saved of $\lfloor n/2\rfloor$. Now say the hats are given uniformly at random. Since each player survives with prob $1/2$, the expected number of survivor is $n/2$. The minimum number of player saved thus cannot exceed $n/2$.