Prisoner Dilemma #2

[m_the0ry]

I found this puzzle while wandering around on the internet. Unfortunately I read the solution right away but I will give you guys some time to try and work out solutions. So the scenario is as follows:

There are some countable number of prisoners, for our case we will arbitrarily pick 100. The prisoners are lined up forward facing, so that they can see only the prisoners in front of them. For example, the man at the back of the line can see 99 prisoners. The man at the front of the line can see zero. Each prisoner is going to be given a white or black hat once they are in line. They cannot see the color of their own hat. Only the hats on prisoners in front of them. The warden begins by asking the prisoner at the back of the line (the one who can see the most other prisoners) to name either 'white' or 'black'. He then proceeds towards the front of the line asking every prisoner to respond 'white' or 'black'. Any other response sends them all back to prison with no hope of parole.

Each prisoner who names the color of his own hat goes free. Those who do not stay imprisoned. Important: Every prisoner may hear the response the other prisoners give, but they do not know whether the response was correct or incorrect.

Assuming the situation is explained fully to the prisoners beforehand, what is the ideal strategy?

[Mark1978]

The prisoner at the back of the line knows his hat colour simply by counting the rest of the hats. The next one hears the previous prisoner call out his hat colour and can make the same deduction from what he hears and sees, and so on down the line.

EDIT: Actually this doesn't work because we don't know how many hats of each colour.

[knowledgeORbust]

I'm probably missing something, but there doesn't seem to be enough information to make a case with either way. There doesn't seem to be any rhyme or reason for how the hats are assigned... if, say, 50% of the hats were black and 50% white, we could build off that. But the colors of the hats in front of you don't seem to matter, assuming there's no obvious pattern, and the ones behind you don't seem to matter either...

Ideal strategy: favorite color? [img]/images/graemlins/laugh.gif[/img]

[Drag]

Prisoners in even positions name the color of the hat of a person who stands in front of them, prisoners in uneven positions name the color of their hat (they learn it from previous answers). Assuming a random distribution of hats this method should set 75 prisoners free in average.

[qwnu]

[ QUOTE ]
Assuming a random distribution of hats this method should set 75 prisoners free in average.

[/ QUOTE ]
Are we justified in doing this?

How about, if you count more of one color in front of you, say that color. If you count the same number of each, say what the guy behind you said.

Of course, if you are in position 100 and you see that 1-50 have black hats and 51-99 have white hats, you'd be a fool to say black. :-(

[luckyme]

can we name the color of the hat in front of us?

luckyme

[foal]

[ QUOTE ]
Prisoners in even positions name the color of the hat of a person who stands in front of them, prisoners in uneven positions name the color of their hat (they learn it from previous answers). Assuming a random distribution of hats this method should set 75 prisoners free in average.

[/ QUOTE ]
Are we assuming they are given opportunity to discuss a strategy as a group, or are we just going with the best strategy for any given individual ignorant of what strategies others might be using?

I'd look for patterns in the hats in front of me e.g. black, white, black, white or to see if there was an uneven distribution e.g. lots of black hats and very few white hats.

Edit: Oops, I guess this means they do have time to plan as a group.

[ QUOTE ]

Assuming the situation is explained fully to the prisoners beforehand, what is the ideal strategy?

[/ QUOTE ]

Your solution sounds good, Drag.

[qwnu]

This reminds me of another similar puzzle. This one is much easier, I think.

The king buries 4 prisoners up to their necks, 3 on one side of a wall, and one on the other. Each faces the wall. He puts a hat on each, as shown. Each can see the hats in front of him, but can't see through the wall:

He says, "There are 2 black hats and 2 white hats among the 4 of you. You will all go free if one of you can tell me which color you are wearing. Otherwise, you will all be executed. No communication is permitted. You have one minute. Begin."

What happens?

[Justin A]

[ QUOTE ]
This reminds me of another similar puzzle. This one is much easier, I think.

The king buries 4 prisoners up to their necks, 3 on one side of a wall, and one on the other. Each faces the wall. He puts a hat on each, as shown. Each can see the hats in front of him, but can't see through the wall:

He says, "There are 2 black hats and 2 white hats among the 4 of you. You will all go free if one of you can tell me which color you are wearing. Otherwise, you will all be executed. No communication is permitted. You have one minute. Begin."

What happens?

[/ QUOTE ]

the guy in back doesn't say anything, which tells the second guy that he doesn't know, which means that he and the first guy are wearing different colored hats.

[qwnu]

Right, so the middle guy on the right correctly deduces his own color and says "My hat is black!" with 5 seconds to go.

Then the king bulldozes them anyway.