Prisoner Dilemma #2
 

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?

Re: Prisoner Dilemma #2
 

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.

Re: Prisoner Dilemma #2
 

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]

Re: Prisoner Dilemma #2
 

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.

Re: Prisoner Dilemma #2
 

[ 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. :-(

Re: Prisoner Dilemma #2
 

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

luckyme

Re: Prisoner Dilemma #2
 

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

Re: Prisoner Dilemma #2
 

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:
http://img169.imageshack.us/img169/802/buriedla5.jpg
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?

Re: Prisoner Dilemma #2
 

[ 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:
http://img169.imageshack.us/img169/802/buriedla5.jpg
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.

Re: Prisoner Dilemma #2
 

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.

Re: Prisoner Dilemma #2
 

I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

Re: Prisoner Dilemma #2
 

Some of you are taking some good stabs at it. I will give you some hints because this is not easy at all.

Regarding the ideal strategy, there is a way to ensure that all but one of the prisoners (99 in this case) are set free, and 50% of the time all 100 of them will be set free.

Second hint, keep in mind that every person can see all of the colors of hats in front of them. That means that the guy in the back of the line knows the most about the situation. His answer space consists of either a 'white' or a 'black'. Consider how we can convey the most information with 2 possible answers.


Hint 3 in white:
<font color="white"> mod2(#ofwhitehats) </font>

Re: Prisoner Dilemma #2
 

[ QUOTE ]
I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

[/ QUOTE ]

this is the correct answer

Re: Prisoner Dilemma #2
 

[ QUOTE ]
I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

[/ QUOTE ]

Pretty sure this is correct. 99.5/100 on average go free unless I'm missing something.

Re: Prisoner Dilemma #2
 

I've got another solution, but it is worse than the one proposed.

Anyway:
First 7 prisoners, communicate in a binary code the number of black hats to the 93 prisoners left (saying black for 1 and 0 for white). Then they can easily deduce their color and correctly predict it.

This soultion can be improved a bit, if first 5 guys give in abinary code the smallest among the number of white hats, number of black hats or the difference between these numbers. This method will set free 97.5 prisoners on average.

Re: Prisoner Dilemma #2
 

[ QUOTE ]
[ QUOTE ]
I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

[/ QUOTE ]

Pretty sure this is correct. 99.5/100 on average go free unless I'm missing something.

[/ QUOTE ]
thats only if the hats are distributed 50/50.

Re: Prisoner Dilemma #2
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

[/ QUOTE ]

Pretty sure this is correct. 99.5/100 on average go free unless I'm missing something.

[/ QUOTE ]
thats only if the hats are distributed 50/50.

[/ QUOTE ]
No.. it should work no matter what. It's only the first guy who may or may not go free.

Re: Prisoner Dilemma #2
 

This solution (originally by ballin4life) is the ideal one

The first prisoner has no way of getting information about his own hat since the distribution is true random. You can convey the parity (even/odd) of the number of white hats with the first prisoner's answer. Black is odd, white is even. Once you have that information, the next prisoner counts up the number of hats and if the number has changed from even to odd or vice versa he knows for certain he has a white hat. If it has not changed he has a black hat. Every other prisoner keeps track of the parity as either even/odd alternating each time someone says 'white' and applying the same algorithm. An average of 99.5 prisoners go free.

Re: Prisoner Dilemma #2
 

[ QUOTE ]
I think the solution should be something like:

If the first prisoner sees an even number of black hats, he calls black. If he sees an odd number of black hats he sayas white. The second prisoner uses the info that the first prisoner saw an even/odd number of black hats to deduce his hat color and so forth.

[/ QUOTE ]

this is the correct answer

btw this type of thread should probably be posted in POG (either in addition to or in place of here)