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.
Darn, after I figured out the solution (it took me a gruelling 4 hours) and wrote it up, I checked the comments to see if it was already posted. Alas it was by OOO. (Much respect). Still for what it's worth, I came up with the answer myself (albeit too slowly). My first idea was to incorporate binary numbers, but that flopped.
My Solution
We can save n-1 prisoners. The guy at the back of the line must be a "Sacrifice". The Sacrifice's job is to count the number of blue hats in front of him and make a "call".
The "call" is based on the following rules. If there are an even number of blue hats, he yells out "blue". If there is an odd number, he yells out "red". By doing this, he tells all the other prisoners whether the number of blue hats (not including his own) is an even or an odd number.
The next person in line looks down the field and counts the number of blue hats. If he counts an even number, and the Sacrifice yelled "blue" to indicate overall "even", then he yells "red". This is because if he counted an even number of blue hats, and he was a blue hat himself, that would make the overall number of blue hats an odd number.
Conversely, if he counts an odd number, and the Sacrifice yelled "blue" to indicate overall "even", then he yells "blue". He has to have a blue hat to make an odd field even up.
From this point on, it is up to each person to do 3 things:
1) Remember the original "call" of whether there are total even or odd blue hats worn.
2) Count the number of blue hats in front of him and decide whether it is even or odd.
3) Keep listening to the number of blue hats called from behind him.
The reason for Rule 3 is though each prisoner cannot see behind them, they can hear. Hearing is the same as seeing in this case. If the original call was "even" and he counts an "odd" field in front of him, and he has heard an "odd" number of blue hats being called behind him (odd number + odd number=even number), then he knows that he is not wearing a blue hat. If he were, the overall field would not be even.
PS - Thanks JDK for the problem, this was a good one. Haven't had this much fun since in a long time.
My Solution
