Prisoner Dilemma #2

[ballin4life]

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.

[m_the0ry]

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>

[dknightx]

[ 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

[ZeeJustin]

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

[Drag]

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.

[xxThe_Lebowskixx]

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

[foal]

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

[m_the0ry]

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.

[durron597]

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