[bushindo]

Let's say that you and 19 other prisoners are on a death row. The warden gives you and your fellow prisoners a chance to win your freedom through a game. The game is as follows,

1) When the game starts, the warden will blindfold all 20 prisoners and arrange them in a circle.

2) The warden will put on each prisoner's head either a RED or a BLACK hat. The warden will choose the color for each prisoner by flipping a fair coin.

3) The warden will then remove the blindfolds. Every prisoner will be able to see the hats on the other 19. Each person will not know the color of his own hat. There are clocks on each side of the room, so every prisoner will be able to see a clock as well.

4) The warden then says, "Everybody should be able to see the hat color of his fellow prisoners. See those clocks? For the next 20 minutes, each person may at any time raise his hand and simultaneously shout out his hat color. At the end of the 20 minutes, if everybody correctly shouted their hat colors, then you all win your freedom. Each person can only shout out his hat color once. If 1 or more person incorrectly shouted his hat color, or if 1 or more person failed to make a guess, then you all go back on the death row."

5) Each person is not allowed to communicate to his fellow prisoners during the game by varying his tone of voice, volume, facial expressions, body language, etc. The warden reserves the right to cancel the game and put everybody back on the death row if he see these types of behavior.

You and your 19 friends have 1 night to discuss a strategy. Find a strategy that makes your chances of freedom as high as possible.

[Guest]

If the Clocks have a reflective surface (Like when you look at yourself in a car window etc.) could all the prisoners look at the clocks, see his reflection and then be able to say the colour of his hat correctly???

It's just a thought...

The prisoners are stood in a circle and there is an even amount (20 prisoners)

They are allowed to raise their hands right? so if they plan to wor with the man directly opposite him (as in being able to co-operate and work with all the men so that once in the circle they could work with the man directly opposite him), they could come up with a plan like this....

If the man opposite him has a red hat they will raise their hand after exactly 5 minutes and if he has a black hat on, he will not raise hi hand. they will then know what colour hat they are wearing and can say it to gain freedom.....

The raising of the hands would have to be done at the exact same time as the men will be blindfolded and therefore wouldn't be able to guarantee which man he would be helping

Also.... only after all those with red hats have spoken their colour would those with black hats be able to speak

Hope this Helps and I think this would work? (Well I hope it would anyway)

Edited August 23, 2011 by MidnightLove7

[bushindo]

If the Clocks have a reflective surface (Like when you look at yourself in a car window etc.) could all the prisoners look at the clocks, see his reflection and then be able to say the colour of his hat correctly???

It's just a thought...

Let's say that the clocks have non-reflective surfaces. Nice out of the box thinking, though.

The prisoners are stood in a circle and there is an even amount (20 prisoners)

They are allowed to raise their hands right? so if they plan to wor with the man directly opposite him (as in being able to co-operate and work with all the men so that once in the circle they could work with the man directly opposite him), they could come up with a plan like this....

If the man opposite him has a red hat they will raise their hand after exactly 5 minutes and if he has a black hat on, he will not raise hi hand. they will then know what colour hat they are wearing and can say it to gain freedom.....

The raising of the hands would have to be done at the exact same time as the men will be blindfolded and therefore wouldn't be able to guarantee which man he would be helping

Also.... only after all those with red hats have spoken their colour would those with black hats be able to speak

Hope this Helps and I think this would work? (Well I hope it would anyway)

This is also interesting out of the box thinking. However, let's assume that each prisoner is required to shout his hat color at the same instant that he raises his hand.

[Molly Mae]

If the Clocks have a reflective surface (Like when you look at yourself in a car window etc.) could all the prisoners look at the clocks, see his reflection and then be able to say the colour of his hat correctly???

It's just a thought...

Someone proposes something like this in every hat puzzle and every time it is against the rules. And then someone comes on and says "Imagine instead that they are isolated in a room..."

The prisoners are stood in a circle and there is an even amount (20 prisoners)

They are allowed to raise their hands right? so if they plan to wor with the man directly opposite him (as in being able to co-operate and work with all the men so that once in the circle they could work with the man directly opposite him), they could come up with a plan like this....

If the man opposite him has a red hat they will raise their hand after exactly 5 minutes and if he has a black hat on, he will not raise hi hand. they will then know what colour hat they are wearing and can say it to gain freedom.....

The raising of the hands would have to be done at the exact same time as the men will be blindfolded and therefore wouldn't be able to guarantee which man he would be helping

Also.... only after all those with red hats have spoken their colour would those with black hats be able to speak

I think the biggest hole here is that when you raise your hand you must shout the colour of your hat.

The best I can come up with is actually the parity answer where one person takes a 50/50 and the circle continues.

I came up with this as I was thinking about it.

Or appoint two people--a primary and a secondary. The primary is going to make a guess when precisely 5 minutes has elapsed, unless the secondary is wearing a red hat. After the 5 minutes has elapsed and the primary hasn't guessed, he will raise his hand and shout red at the end of another 5 minutes (the number of minutes is arbitrary) unless shouting red throws off the parity (say the parity is defaulted to 0--he sees an even number of red hats). If, at the end of 10 minutes, the secondary has not shouted, the primary will shout red if he sees an odd number of red hats (he now knows the parity).

*note: this is very poorly worded, but it works. After those two have established the parity, everyone will know the colour of his own hat..

Edited August 23, 2011 by Molly Mae

[Guest]

agree to raise your left arm if the prisoner across from you is red, and the right arm if black.

[bushindo]

Someone proposes something like this in every hat puzzle and every time it is against the rules. And then someone comes on and says "Imagine instead that they are isolated in a room..."

I think the biggest hole here is that when you raise your hand you must shout the colour of your hat.

The best I can come up with is actually the parity answer where one person takes a 50/50 and the circle continues.

I came up with this as I was thinking about it.

Or appoint two people--a primary and a secondary. The primary is going to make a guess when precisely 5 minutes has elapsed, unless the secondary is wearing a red hat. After the 5 minutes has elapsed and the primary hasn't guessed, he will raise his hand and shout red at the end of another 5 minutes (the number of minutes is arbitrary) unless shouting red throws off the parity (say the parity is defaulted to 0--he sees an even number of red hats). If, at the end of 10 minutes, the secondary has not shouted, the primary will shout red if he sees an odd number of red hats (he now knows the parity).

*note: this is very poorly worded, but it works. After those two have established the parity, everyone will know the colour of his own hat..

Your strategy is not optimal yet. It is a good beginning step, though

So, your strategy requires the primary person to raise his hand and guess at 5 minutes into the game if the secondary person has a BLACK hat (1 in 2 chance). So, suppose that the secondary person does have a BLACK hat, then the primary person have a 1/2 chance of guessing correctly. That means your strategy would result in 1- (1/2)*(1/2) = 3/4 winning rate.

This is a good start. However, the optimal winning rate is much higher than 3/4.

agree to raise your left arm if the prisoner across from you is red, and the right arm if black.

You found a loophole that I didn't think about when I tried to box the out-of-the-box solutions. Having a choice of which arm to raise is not intended in the OP, however, I don't see how it can help improve the winning rate beyond strategies like Molly Mae's. Can you flesh out your strategy so that we can compute a winning rate?

[Guest]

Select one prisoner to begin. Have the prisoner 10 from him clockwise stare at the clock if his hat is red, and at the table if his hat is black. The prisoner that begins then raises his hand and states his hat color. Each prisoner in clockwise area repeats the process, until all prisoners are done.

[CaptainEd]

The team of 20 will identify a leader. The first 15 people starting with the leader will follow the approach spelled out in "Team of 15". So in a large fraction of the cases, one person will be able to announce his hat correctly. From now on, we refer to that announcer as A, and label each of the players clockwise B, C,...T.

A announces his own hat color at minute 1:00 if B wears black, minute 2:00 if red.

From now on, all activities happen on 15-second ticks. B announces at one tick (1:15 or 2:15) if C wears black, but at two ticks (1:30 or 2:30) if C wears red.

This takes at most 12 minutes. Everybody has claimed. It works in those large number of cases where the Team of 15 works.

For the details of the Team of 15 approach, see

Edited August 24, 2011 by CaptainEd

[CaptainEd]

Use the Team of 15 approach as before. Player A announces his/her hat color at 1 minute if parity over the team of 20 is even and 1:30 if odd. Then everybody can compute their own color and announce any time they want.

[bushindo]

Select one prisoner to begin. Have the prisoner 10 from him clockwise stare at the clock if his hat is red, and at the table if his hat is black. The prisoner that begins then raises his hand and states his hat color. Each prisoner in clockwise area repeats the process, until all prisoners are done.

I think this would violate provision 5) in the OP, which states that each person is not allowed to communicate to his fellow prisoners during the game by varying his tone of voice, volume, facial expressions, body language, etc. Also, please consider using spoiler for your answers since other people may want to work on the solution on their own.

Use the Team of 15 approach as before. Player A announces his/her hat color at 1 minute if parity over the team of 20 is even and 1:30 if odd. Then everybody can compute their own color and announce any time they want.

This is a huge improvement over the previous bar set by Molly. It is still sub-optimal, although you're approaching the ceiling

The use of the solution for 'Team of 15' is very creative. I did not think of that possibility at all. The chance of announcer A successfully guessing his hat color and thereby winning the game is 15/16, or about 93.75%.

It is possible to get a winning rate that is over 99%, however.

[CaptainEd]

We sacrifice one position: all Black. Thus, assuming the fair die, the win probability is 1-2^(-20)

At some point, all the people wearing Red will say so.

Here's how that works. We proceed as follows, until the first R announcement. Then the rest of the people announce B.

Starting with N = 19, anybody who sees N B will announce R at time (20 - N).

That is, a person who sees 19 B announces R at time 1. There's only one such person, because everybody else sees 18B. (unless they all have B, in which case they're dead).

But if nobody speaks at time 1, then there are fewer than 19. If there are 18, two people will speak at time 2 (because they are the ones who only see one R; the others see 17 B and 2 R)

If there are 17, three will speak at time 3.

...

If there is only 1 B, 19 will speak at time 19.

If they are all red, all 20 will speak at time 20. If that is cutting it too close, this last call can be made at 19:30.

Thank you, Bushindo, for another surprise. I would not have imagined this result!

[witzar]

Let's give the prisoners numbers from 1 to 20.

Let w be a number of white hats, and let w(i) be the number of white hats seen by prisoner number i (for i=1, 2, ..., 20).

The strategy for prisoner number i is to wait w(i) minutes, then raise a hand and claim his hat color to be:

a) white, if no prisoner raised a hand before him

b) black, otherwise.

That's it.

For w=0 (only black hats) this strategy fails making all prisoners to say "white" at the beginning.

For w>0 this strategy ensures to save the prisoners.

Note that that w(i) = w for prisoners with black hats and w(i) = w - 1 for prisoners with white hats.

Therefore if w>0 then w(i)>=0 for every i.

So in case w>0 each prisoner with white hat will say "white" exactly (w-1) minutes after beginning, and exactly one minute later each prisoner with black hat will say "black".

Since warden tosses fair coin to assign hats colors, the probability of a success of this strategy is 1 - 0.5^20.

[Guest]

Could all of them just look up at there hats??

[Molly Mae]

We sacrifice one position: all Black. Thus, assuming the fair die, the win probability is 1-2^(-20)

At some point, all the people wearing Red will say so.

Here's how that works. We proceed as follows, until the first R announcement. Then the rest of the people announce B.

Starting with N = 19, anybody who sees N B will announce R at time (20 - N).

That is, a person who sees 19 B announces R at time 1. There's only one such person, because everybody else sees 18B. (unless they all have B, in which case they're dead).

But if nobody speaks at time 1, then there are fewer than 19. If there are 18, two people will speak at time 2 (because they are the ones who only see one R; the others see 17 B and 2 R)

If there are 17, three will speak at time 3.

...

If there is only 1 B, 19 will speak at time 19.

If they are all red, all 20 will speak at time 20. If that is cutting it too close, this last call can be made at 19:30.

Thank you, Bushindo, for another surprise. I would not have imagined this result!

Yeah. Answer similar to an Escape the Island ("I see someone with blue eyes") puzzle. Very nice puzzle bushindo. And great solve, Captain.

[Guest]

Have everyone pair up with a partner. Then assign an order to the partnerships. Let's call the partnerships A, B, C,.... and the members of each partnership as A1, A2, B1, B2, etc.

So the strategy is that when the blindfolds are removed, A starts and each A1 and A2 obviously look at their partner's hat color and at 15 sec (or some agreed number of seconds) and raise their hand if the hat color of the partner is red. If neither raises their hand then they both know that their own hat is black and after 5 seconds A1 raises his hand with Black and A2 then follows with Black. So if they are both red both will raise their hands at the same time and yell out red. If A1 raises his hand with no movement on the part of A2 then A1 shouts Black followed by A2 raising his hand to shout out Red. This process then continues with team B starts at exactly 30 seconds, C at 45 seconds, etc.

Everyone gets it right and lives!

[BobbyGo]

Have all of the prisoners raise their hand and shout a random color at the same time. The guards won't know who shouted what, and they are all released and eat ice cream.

[bushindo]

Congratulations to CaptainEd and witzar for the nice solve. I'm glad you enjoyed the puzzle. I'm working on another one and will post it soon.

[Guest]

The probabilty on any coin flip is 50/50. Probability is based on a set of circumstances that is going to happen. Unless it has been communicated to the lead prisoner as to which hat he is wearing, he is only calling the coin flip for him,

[Guest]

I think imhere and joe p has a good idea, if im reading it right, his strategy would work, everyone in a circle, (like a clock) : ) prisoner 1 standing in the 12 o clock position, "partners up" with prisoner 2 standing at the 6 o clock position, P1 sees that P2's hat is red, so he raises his right hand (for red), at the same exact time P2 raises his left hand (for black) letting P1 know his hat color is black. They both are now able to shout out their hat color, This will continue all the way around "the clock" formation. I see no reason why this would not work, also op says

"each person may at any time raise his hand and simultaneously shout out his hat color"

Edited August 24, 2011 by Barron

[Guest]

If they can't communicate with each other and there is no place for wrong answer.....I think the highest probability they can get is 50%... because the 1st person who will raise his hands will have a 50% chance to get the right..even if he guess it right... And based on the previous answers which have the time interval of 15 secs or something which have a 100% chance for the 2nd to last prisoner to guess the right color.... It will still be 50%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%x100%=50%

therefore 50% is the highest chance