2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is there any restriction on number of colours used. There must be, else you can't solve. $\endgroup$ – user67773 May 8 '13 at 7:58
  • $\begingroup$ I have seen such a problem, where no of prisoners are 5. No. of black hats=3 and white=4.Then it is a question of probability. $\endgroup$ – ABC May 8 '13 at 7:59
  • 1
    $\begingroup$ @Anonymous: Do mention that in your question. $\endgroup$ – Inceptio May 8 '13 at 8:09
  • 3
    $\begingroup$ Unless a distribution is specified, the best strategy seems to toss a fair coin and call out a color. Suppose there is another strategy which does better, it's easy to apply the same strategy and flip colours while distributing, thereby defeating that strategy. $\endgroup$ – Macavity May 8 '13 at 9:20
  • 1
    $\begingroup$ Here's a more detailed argument that the answer can't be independent of the distribution. If the number of white hats is known to be even, all prisoners can deduce their colour, and if it's known to be odd, they can also deduce their colour, but the result is the opposite. So a strategy that is optimal for one distribution is the worst for another distribution and vice versa. Thus there is no such thing as "the most efficient strategy" independent of the distribution. Are you sure that the intended meaning of the question isn't that the hat colours are independently uniformly distributed? $\endgroup$ – joriki May 8 '13 at 14:55
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Or if the hats are split 50–50, then nobody gets out and the warden has a good laugh at everyone else's expense. $\endgroup$ – MJD May 10 '13 at 2:07
  • $\begingroup$ Actually, if the hats are split 50-50 then 50% people get out, just like in the case of a coin toss, because then they should actually toss a coin to come up with an answer. $\endgroup$ – OC2PS May 10 '13 at 2:13
  • 2
    $\begingroup$ @OC2PS The problem is that if the split is 50-50 then everyone sees a majority of the hats that are not their color - they see 50 hats of their color and 49 of the other - so they always guess wrong. $\endgroup$ – Steven Stadnicki Jul 24 '13 at 19:02
-1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first paragraph is correct and looks good to me; but I don't understand the optimality argument in the second half. The hats may be randomly distributed, but that doesn't mean that there's no information to be gleaned there... $\endgroup$ – Steven Stadnicki Jul 24 '13 at 19:03
  • $\begingroup$ @StevenStadnicki The answer shows that, assuming worst-case scenario, you can save $n/2$ persons. Now if you have some info on the distribution you can sure use it but I don't think the warden will want to unveil it's hats beforehand $\endgroup$ – Jean-Sébastien Jul 24 '13 at 21:12
  • $\begingroup$ It is optimal the sense that no strategy can make it save under $n/2$ persons, wheras betting on the majority has a weakness $\endgroup$ – Jean-Sébastien Jul 24 '13 at 21:20
  • $\begingroup$ I think, the idea is to save yourself, not to save the population :-) $\endgroup$ – OC2PS Aug 31 '13 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.