[bonanova]

Warden Jones has informed 100 prisoners that tomorrow

is their day of reckoning.

For a clearer statement of this puzzle, please click here.

They will be led into a courtyard and the warden will

place a black or a white hat on each or their heads.

No prisoner will see the color of his own hat, but

each will see the color of all 99 of the other hats.

The prisoners will be given a pencil and a piece of paper.

They will each write W or B on the paper. The warden will

go to prisoners at random and read what has been written.

If it matches the color of the prisoner's hat [W-white or

B-black] the prisoner will be set free. If it does not match,

the prisoner will be executed on the spot.

Tomorrow the prisoners will not be permitted to

communicate with each other in any way. They will

be permitted to look at any of the other hats, and

to write a W or B on their paper and nothing else.

The prisoners are meeting tonight to form a strategy.

They have called you to their meeting as an expert

logician to assist them.

How many prisoners can you guarantee will be set free?

[Guest]

One clarification needed.

Let say the first random prisoner is chosen. Whatever his answer is, right or wrong. Can the other prisoners change their answers after that?

Then 99 can be guaranteed to be saved

[bonanova]

One clarification needed.

Let say the first random prisoner is chosen. Whatever his answer is, right or wrong. Can the other prisoners change their answers after that?

Then 99 can be guaranteed to be saved

What's written on the paper is final.

Everyone writes on his paper before the first paper is read.

[Guest]

99. They can draw the name of one person who will sacrifice for others. Then since anyone can look at anyones hat. What he can be made to do is to look to his immediate right persons hat if white are odd and look to left if even. Then the same strategy. All others can look at him.

[Guest]

Could this be considered as a means of communication between the prisoners???

100% save guaranteed. My advice for them would be to be in a line side by side. The first person will stand in either direction. The next person will then stand facing the same direction as the first one if the first person's hat is W and in the opposite direction if it is B -- the first person will write 'W' or 'B' depending on the position of the person to his left (or right) whichever direction you consider. This procedure will enable all the prisoners, except the last (rightmost or leftmost) one to know the color of their hat. Then the second from the last will change or stick on his position depending on the color of the last prisoner.

P1 P2

/\ /\ ==> the first person knows the color of his hat is white.

/\ V ==> the first person knows the color of his hat is black.

Edited April 1, 2008 by brhan

[EventHorizon]

what would you define communication as?

would walking up to someone and turning your back on them be considered communication? Would kicking someone be considered communication? How about eye contact? Would anything that could be used to give any information be considered as communication?

[Guest]

what would you define communication as?

would walking up to someone and turning your back on them be considered communication? Would kicking someone be considered communication? How about eye contact? Would anything that could be used to give any information be considered as communication?

Hmmm scary ... hope this questions are not meant to me

[Guest]

i need to know what you mean by "communication".. ü

but here is my crude answer:

100% can be saved. Group the prisoners into pairs each having a designated partner the night before. These partners will have to verify the color of the hat of their partner the next day. supposing all could write (since the condition is to write W or B), they must use their left hand if the color of the hat of their partner is White or use the right hand if the color of the hat is Black. by this method, a prisoner will know the color of his hat and he will "tell" the color of the hat of his partner. (a right handed man can use his left hand in writing and vice versa; although the letters that will be written are not that legible) and another thing; this partners MAY not stay together but will stay at a point where they will see each other to avoid suspicion.

[Guest]

using the same technique as before (the pair technique):

instead of using the right hand, left hand stuff;

a prisoner must sit (if permitted) if the color of the hat of his partner is black or simply stand if the color is white.

there are other methods too, if the pair method is a permitted method:

-if it is not permitted to sit, stand straight, and put your feet together if the color of the hat of your partner is white and put your feet apart (but not so apart so you won't look like a lost gymnast)if the color is black.

-and other stuff that can show if the color is black or white.

of coure, i still don't know if these falls under the jurisdiction of your "communication"..

ü

[bonanova]

All I can say so far is that you guys are smarter at getting around a restriction on communication than I am at prohibiting it.

So I've restated in a way that negates all previous answers [sorry, but ... no communicating means no communicating]

and makes it clear what you CAN do.

Here goes.

Tomorrow, each prisoner will remain in his cell.

He cannot see and he cannot hear any other prisoner.

The warden will visit each cell and place a hat on the prisoner.

The hat will be black or white.

The prisoner will not know his hat's color and he may not look at it, or determine it by any other manner.

When all 100 prisoners will have received their hats, the warden will go to his office and type a list of all prisoners and the hat colors.

He will then distribute copies of the list to each prisoner - with that prisoner's name and color totally and irretrievably erased.

The warden will then visit each cell and asks the color of that prisoner's hat.

If the answer is correct [i.e. black or white, appropriately] the prisoner will be set free; he will be executed if not.

Tonight the prisoners ask you for guidance in forming a strategy.

How do you advise, and how many do you anticipate you can save from execution?

I've edit the OP to point to this post.

[Guest]

All I can say so far is that you guys are smarter at getting around a restriction on communication than I am at prohibiting it.

So I've restated in a way that negates all previous answers [sorry, but ... no communicating means no communicating]

and makes it clear what you CAN do.

Here goes.

Tomorrow, each prisoner will remain in his cell.

He cannot see and he cannot hear any other prisoner.

The warden will visit each cell and place a hat on the prisoner.

The hat will be black or white.

The prisoner will not know his hat's color and he may not look at it, or determine it by any other manner.

When all 100 prisoners will have received their hats, the warden will go to his office and type a list of all prisoners and the hat colors.

He will then distribute copies of the list to each prisoner - with that prisoner's name and color totally and irretrievably erased.

The warden will then visit each cell and asks the color of that prisoner's hat.

If the answer is correct [i.e. black or white, appropriately] the prisoner will be set free; he will be executed if not.

Tonight the prisoners ask you for guidance in forming a strategy.

How do you advise, and how many do you anticipate you can save from execution?

I've edit the OP to point to this post.

So to clarify, no communicating between prisoners after the meeting and no changing your answer after the executions have started!!! I'm assuming you can't co-opt a guard or non-prisoner? Is the prisoner's position in the list preserved even if his name and hat color are not? Are the prisoners allowed to communicate after they've guessed right?

If you are allowed to change your answer after the executions you could buddy up and write the color of your buddies hat. 50% guaranteed (assuming the prisoners are honest... mmm... ) survival (75% average) and technically wouldn't it be the warden that's communicating.

[bonanova]

So to clarify, no communicating between prisoners after the meeting and no changing your answer after the executions have started!!! Correct.

I'm assuming you can't co-opt a guard or non-prisoner? Correct.

Is the prisoner's position in the list preserved even if his name and hat color are not? List of names and hat colors. Yours is erased. Ditto for others.

Are the prisoners allowed to communicate after they've guessed right? No.

If you are allowed to change your answer after the executions you could buddy up and write the color of your buddies hat. 50% guaranteed (assuming the prisoners are honest... mmm... ) survival (75% average) and technically wouldn't it be the warden that's communicating.

To clarify about the list:

if there were four prisoners named Al, Bob, Chuck and Dave, for example,

the warden might go to Al's cell and give him a black hat, go to Bob's cell and give him a black hat, go to Dave's cell and give him a black hat, go to Chuck's cell and give him a white hat.

He would then go to his office and type up a list. It could be in any order. He might choose to alphabetize it, but he doesn't have to.

The list might look like this.

Al - black

Bob - black

Chuck - white

Dave - black

Al would see:

Bob - black

Chuck - white

Dave - black

Bob would see:

Al - black

Chuck - white

Dave - black

Chuck would see:

Al - black

Bob - black

Dave - black

Dave would see:

Al - black

Bob - black

Chuck - white

[Guest]

I have no idea besides the 50% probability of having 2 choices. I am loving coming back to this post though because it is quite entertaining to see the different ideas being brought forth, and your ability to get around them. Great Post!!!

[bonanova]

I have no idea besides the 50% probability of having 2 choices.

I am loving coming back to this post though because it is quite entertaining to see the different ideas being brought forth, and your ability to get around them.

Great Post!!!

I hope I'm not exposing too much of a "sneaky" character trait here...

I'm actually trying to be transparent about the constraints.

But your observation about 50% expectation is absolutely correct!

Now that the problem statement has been reduced to what looks like a coin flip,

the strategy should be crafted to live with a 50% expectation, but nevertheless

make the worst case scenario as good as possible.

If it just remains a coin flip, the worst case is that they all could be executed.

The idea is to see how many prisoners can be guaranteed a pardon.

[Guest]

Hi, new here.

Quick question, can the prisoners move around and see other hats once they have their hats (while the warden is typing the list)?

Using Al, Bob, Chuck and Dave again. Al only looks at Bob, Bob only looks at Chuck, Chuck only looks at Dave, and Dave only looks at All. Then Al goes to the left side of the yard if Bob has a black hat, right side if he has a white hat. Bob does the same, etc. Then you just have to know who is watching you and which side of the yard they moved to. To save them all make sure the last in line looks at the firsts. Once they move around they can all determine their own hat color and write it down.

[Guest]

If you see more than 51 (ie; 52-100), then pick the bigger number.

Because, if Whites are 53, and Blacks are 47. Whites would see 52. Blacks see 53 (for whites). If everyone picks white, at least 52 would survive.

50,51 are tricky.

I still haven't figured out a good solution yet for that.

Edited April 3, 2008 by PolishNorbi

[Guest]

another problem as stated in the revised OP is that there may not be a true 50/50 split of the color. the warden may be a punk and give out more of one color then the other throwing off the thinking that I would go with the minority color on the list. if a true 50/50 split then the answer is easy, count the whites and then count the blacks go with the color that only has 49 on your list (you would be the odd man out). I still have no clue.

[bonanova]

If you see more than 51 (ie; 52-100), then pick the bigger number.

Because, if Whites are 53, and Blacks are 47. Whites would see 52. Blacks see 53 (for whites). If everyone picks white, at least 52 would survive.

50,51 are tricky.

I still haven't figured out a good solution yet for that.

Great thinking ... It looks at first like more than half could be certain of survival.

worst case?']Say it's 51B and 49W,

Everyone would see a majority of black [either 51-48 or 50-49] and pick black.

51% would survive.

It gets even better if the balance is worse:

For 90B and 10W

Everyone would pick black, and 90 would survive.

But ... suppose the sly old warden knew of that strategy.

He would make it exactly 50B and 50W!

Then the blacks would see a majority 50-49 of whites, and

the whites would see a majority 50-49 of blacks!

Oh no!!! all 100 would pick wrong and die.

I don't think you can tweak the strategy for that special case.

If I see 50 white and 49 black, you might think you're black and the split is 50-50.

If so, you should say black.

But you could be white and the split is 51W 49B.

In that case you should say white.

Maybe there's more you could do in the 50-49 case.

I haven't thought it through to the end...

[bonanova]

another problem as stated in the revised OP is that there may not be a true 50/50 split of the color. the warden may be a punk and give out more of one color then the other throwing off the thinking that I would go with the minority color on the list. if a true 50/50 split then the answer is easy, count the whites and then count the blacks go with the color that only has 49 on your list (you would be the odd man out). I still have no clue.

Great observation.

It seems there is an adequate strategy - yours and PolishNorbi's - if you know

[1] the split is 50-50 or if you know

[2] the split is not 50-50.

You need to advise the prisoners on the best strategy that will work whether it's [1] or [2].

When you find it, you'll slap your forehead. Maybe.

[Guest]

I think it is now very simple. Or maybe I am thinking two stupidly

Tell everyone to write white unless one of the colours is at least 2+the other colour.

So if it is 50-50

White will see 50B-49W and Black will see 50W-49B and 50 will be saved.

if its 51W-49B then 51W will be saved.

if its 51B-49W then 49 will be saved.

Other cases are straightforward.

So in the worst case 49% will be saved

Edited April 4, 2008 by imran

[Guest]

I think it is now very simple. Or maybe I am thinking two stupidly

Tell everyone to write white unless one of the colours is at least 2+the other colour.

So if it is 50-50

White will see 50B-49W and Black will see 50W-49B and 50 will be saved.

if its 51W-49B then 51W will be saved.

if its 51B-49W then 49 will be saved.

Other cases are straightforward.

So in the worst case 49% will be saved

If this scenario occured:

51B-49W,

Whites would see: 51-48, and you state 2+ of the other one colour, pick that color. That would lead white to pick black, all white die.

Black see: 50-49, and they would all pick White. All Die.

Since the wardant probably knows the strategy, he would choose that as his solution.

[bonanova]

Hi, new here.

Quick question, can the prisoners move around and see other hats once they have their hats (while the warden is typing the list)?

Using Al, Bob, Chuck and Dave again. Al only looks at Bob, Bob only looks at Chuck, Chuck only looks at Dave, and Dave only looks at All. Then Al goes to the left side of the yard if Bob has a black hat, right side if he has a white hat. Bob does the same, etc. Then you just have to know who is watching you and which side of the yard they moved to. To save them all make sure the last in line looks at the firsts. Once they move around they can all determine their own hat color and write it down.

Yah, that works, Unist, but it's a form of communicating, and the warden says that's a no-no.

Keep thinking, and remember the expectation without communicating is only 50%.

So try to come up with a way that no fewer than 50% are guaranteed freedom.

[bonanova]

another problem as stated in the revised OP is that there may not be a true 50/50 split of the color. the warden may be a punk and give out more of one color then the other throwing off the thinking that I would go with the minority color on the list. if a true 50/50 split then the answer is easy, count the whites and then count the blacks go with the color that only has 49 on your list (you would be the odd man out). I still have no clue.

The warden never said it would be 50/50. If the prisoners knew it was 50/50, the best strategy would be everyone picking white. [or everyone picking black].

[Guest]

The warden never said it would be 50/50. If the prisoners knew it was 50/50, the best strategy would be everyone picking white. [or everyone picking black].

if the prisoners knew it was 50/50 they should count up the number of blacks and whites on the list and pick the color that only has 49 listings!

[Guest]

So, with what everyone's written so far....

If you see 52 or more hats of one color, then you know that everyone is seeing at least 51 or more hats of that color, and everyone should choose the majority color.

If you see 50 or 51 hats of one color, then there's no ideal solution without communication. You should predetermine that if the warden is this mean, everyone just guess white (or black). That way, worst case, 49 people will survive.

[bonanova]

OK here it is ...

There is a strategy that will guarantee 50% survival whatever the warden does.

What is it?

This solution is really quite clever.

And having said that of course, I have to disclaim ownership of it.