[bonanova]

Warden Smith has been transferred to yet another prison, and pity his new set of prisoners!

This time he announces that: tomorrow ...

• they will be taken to the courtyard and arranged in a circle.
  
• each prisoner will be given a white or black hat as determined by a fair-coin toss.
  
• each prisoner will be able to see the hats on all the other prisoners.
  
• no prisoner will be able to see his own hat.
  
• no communication will be permitted.
  
  
  Then,
  

  • unless at least one prisoner guesses, and
    
  • every prisoner who does guess guesses correctly,
    

  all the prisoners will be executed.

  That is, if they all pass, or if anyone guesses incorrectly, they're all dead.

  That makes the prisoners desperate enough to call you in as a consultant.

  You meet with them the night before the event, to advise them what to do.

  One prisoner suggests that they will have an even chance of survival if one person guesses, and all the others pass.

  What do you advise?

  Edit - added 4:50 pm EDT 30 May 2008

  Starter suggestion - suppose there are only 3 prisoners.

  Work out strategies that might improve on the 50% that seems intuitive.

  Then try out your strategy for 16 15 prisoners, where survival could be quite likely.

[Guest]

Clarification: "each prisoner will be given a white or black hat as determined by a fair-coin toss."

Does this mean that it is theoretically possible that every prisoner has a white hat or a black hat? Or will there definitely end up being 50 white hats and 50 black hats determined randomly?

If it's really a 50/50 chance, meaning that there's no guarantee that there will be 50 white hats and 50 black hats (only a 7.96% chance), then I can't see a better chance than the suggestion given. Of course, I know being a bonanova problem that there is a better suggestion.

[Guest]

Question- Is each prisoner allowed to answer only once? That is, if I pass now, will I get a chance to try to answer again later (to guess my hat color), or does my turn come only once?

[Guest]

I can get them to a 75% chance of survival:

For the first person who has to guess, if the person next to him (going clockwise) has a white hat then he passes. If his neighbor has a black hat, then he guesses his own color.

This means that if his neighbor has a white hat (50%), then he'll pass. This would let the next guy know to guess white and all the prisoners are free. If his neighbor has a black hat, then the first prisoner has a 50% chance of getting his right (50% of 50% = 25%).

Thus giving them an overall 75% probability of living.

Of course, this assumes that the other prisoners know when someone passes.

[Guest]

Question -- While there is no communication allowed, what about the responses to white/black/pass? Do all the prisoner's hear the responses?

[Guest]

Assuming that the prisoners know what other guys have guessed, this might be the solution:

In this case, the possible combinations are 5-5, 6-4, 7-3, 8-2, 9-1, 10-0

The first prisoner who starts only guesses if he sees 9 other hats of the same colour. If this is the case, he will guess his own colour to be the opposite (basically 9-1), so if the distribution is 10-0, he is wrong. If he doesn't find other 9 hats to be of the same colour, he passes. The next prisoner knowing that the previous guy has passed is capable of replying to the cases 9-1 and 8-2. Following the same logic, the next one for 8-2 and 7-3. So if 4 guys pass, the 5th one can safely assume that its 5-5, and hence answer accordingly. So they all only die if its 10-0.

[bonanova]

Fair coin toss means a coin is tossed for each prisoner.

If it's heads [say] he gets a black hat. If it's tails he gets a white hat.

One can conclude that there is no guarantee of equal numbers.

The prisoners are taken aside and asked to guess [or pass.]

No communication is permitted.

One can conclude that prisoners do not know the response given by other prisoners.

Each prisoner answers only once. [implied but explicit in OP]

Net: each prisoner's strategy is guided only by what he sees.

I've added this starter suggestion to the OP:

Starter suggestion - suppose there are only 3 prisoners.

Work out strategies that might improve on the 50% that seems intuitive.

Then try out your strategy for 16 prisoners, where survival could be quite likely.

[Guest]

Let the strategy be: if you see both of your fellow prisoners with the same hat, guess the other color. If you see one of your fellow prisoners with a black hat and one with white, do not guess.

What this would do would create a scenario that of the 8 possibile hat permutations with 3 prisoners, that if they all had the same hat color, all would answer the wrong way and all would die. But, in the other 6 scenarios (2 one color, 1 other), 2 wouldn't guess, 1 person would and would guess correctly, and all would live.

Not sure how to apply this yet to the whole thing, but I might be gone until Monday, so hopefully this helps someone.

[Guest]

i think i might have a answer..

ok,

i assume poeple are allowed to move there head left or right slightly while they are all standing in the circle. if not move there head, then move their eyes or something so they actually get to see everyones hat.

pick 1 guy and all other poeple pass.

while this one guy is standing in the circle, the person left to him will look at the chosen one and the guy next to him, if the 2 hats are same colour, he keeps staring in that direction. if the 2 hats are different he looks other way constantly.

chosen one will look to both sides, if guy on left is looking at him he has same colour as guy on right.

if guy on left is not looking at him, then he has opposite to guy on right.

all pass, chosen one knows, 100% success

is that right or am i missing something

Edited May 30, 2008 by calis16

[EventHorizon]

i think i might have a answer..

ok,

i assume poeple are allowed to move there head left or right slightly while they are all standing in the circle. if not move there head, then move their eyes or something so they actually get to see everyones hat.

pick 1 guy and all other poeple pass.

while this one guy is standing in the circle, the person left to him will look at the chosen one and the guy next to him, if the 2 hats are same colour, he keeps staring in that direction. if the 2 hats are different he looks other way constantly.

chosen one will look to both sides, if guy on left is looking at him he has same colour as guy on right.

if guy on left is not looking at him, then he has opposite to guy on right.

all pass, chosen one knows, 100% success

is that right or am i missing something

no communication...it would be way too easy otherwise

[bonanova]

Let the strategy be: if you see both of your fellow prisoners with the same hat, guess the other color. If you see one of your fellow prisoners with a black hat and one with white, do not guess.

What this would do would create a scenario that of the 8 possibile hat permutations with 3 prisoners, that if they all had the same hat color, all would answer the wrong way and all would die. But, in the other 6 scenarios (2 one color, 1 other), 2 wouldn't guess, 1 person would and would guess correctly, and all would live.

Not sure how to apply this yet to the whole thing, but I might be gone until Monday, so hopefully this helps someone.

You have the optimal strategy for 3 players.

Note that 3 is 1 less than a power of 2, and for such cases, the odds become very favorable.

Now, can you generalize it to 7 or 15 prisoners?

the incorrect answers are packed into as few configurations as possible.

For n players you'd like to do the same: have just two kinds of configurations:

• good ones, where just one prisoner guesses [correctly] and the other pass and
  
• bad ones, where everyone guesses, and they all guess wrong.
  

That makes efficient use of correct guesses and crams the wrong guesses into as few configurations as possible.

In fact, the good configurations would outnumber the bad configurations by a factor of n, giving a winning

probability of n/(n+1) -- in this case [n=3] it's 75%

It turns out that this optimum solutions obtains if and only if (n+1) evenly divides the number of configurations 2ⁿ,

which means that n must itself be 1 less than a power of 2.

The key is to find a set of bad configurations [in the 3 case, it's all the same color] that has the property that

every other configuration is adjacent to exactly one bad one - adjacent means you can get from one to the

other by changing the color of one hat.

[bonanova]

[1] If a prisoner sees hats of different colors, he will pass

[2] Otherwise he will guess the color that he does not see.

In six cases: BBW BWB BWW WWB WBW and WBB, the odd prisoner will guess correctly while the others pass. That's a win, and they all go free.

In two cases: BBB and WWW, all the prisoners guess. And they all guess wrong. And they are all executed.

That's a 75% expectation of survival!

Why does it work?

All the dirt is swept into 1/4 of the room, so to speak, leaving 75% of the room clean.

The dirt is the wrong answers.

Looking at the 8 possible configurations, 12 prisoners will guess their color. 6 will be correct; 6 will be incorrect.

The 6 incorrect guesses are all crammed into 2 of the 8 configurations, leaving 6 of the 8 configurations clean.

The trick for n>3 prisoners is to find a strategy that crams the half of the guesses that will be incorrect into as few configurations as possible.

With the solution for 3 prisoners now elucidated, you have some guidance.

What is the solution for 2^k - 1 prisoners? [k is ingeter >2]

What is the general solution for n>3 prisoners?