A group of prisoners is under sentence of death and the warder decides to give them a test to gain their freedom. He tells them, "I will place a red or blue hat on each of your heads and then I'm going to arrange you in random order in a row so that no prisoner will be able to see his own hat but each one will see all the hats in front of him. Starting with the guy at the back each of you in turn must loudly say what color hat you think you have. Correct answers will go free, incorrect ones will be thrown to the alligators in the moat. I will give you time for a brief meeting before we start, so you can plan your optimum strategy."

What strategy can the prisoners - there are N of them - adopt to improve their odds above 50:50?

Hint: They need to agree on a strategy which allows each person to identify his/her own hat while simultaneously providing as much information as possible for all those in front.

let us say blue = +1 and red = -1

now the last person will multiply all the hats before him and will shout the result..    (it would be either +1 or -1 implies blue or red)

in this way last person may or may not live..but the second last person will certainly has the correct answer i.e. the color of his hat.... how ? ... he will multiply all the hats before him and will deduce the color of his cap on the basis of last man's result..

example ... last man's result was -1  (odd number of red caps)

and the second last man's is +1 .. it means he must be having -1 on his head.. other wise last man would not had shouted -1...

and so on everybody would identify the color of their caps....and hence everybody except the very last one will live.

Posted by ritesh on 2007-11-14 02:33:29