Problem of the Week

This week's problem was suggested by Tim Ellis.  Many thanks.

You are the leader of a group of 100 people who have been taken captive.  Your captor has told you that tomorrow your group will be put into a single file and each person will have either a white hat or a black hat placed on his head.  Each person will be able to see all the hats in front of him, but not those behind or on his own head.  Your captor will then start at the back of the line and ask each person, in turn, for the color hat of the hat on his own head.  If the person responds with the correct color, his life will be spared, otherwise he will live in captivity forever.

As the leader of the group you will have until tomorrow to develop a strategy for the group to carry out and which will free as many people as possible.  After the group is in line, no further communication is allowed, except that all will hear each person's response to the question about the color of his hat and whether the response was or was not correct.

What is the best strategy?  Can you prove that this is, indeed, the best strategy?  (Ignore human frailty, and nerves, and assume that whatever strategy you come up with will be perfectly carried out. )

For example, suppose your strategy is that every other person say the color of the hat of the person immediately in front of him.  The first person has a 50/50 chance of being right, while the second, having just been told the color of his hat, is sure to go free.  With this strategy 75% of the group, on average, will be freed -- half will be sure to go free while the other half will be free with a probability of 50%.  Can you do better?

You are visitor number 4422 to this page.
©MM Alberto L. Delgado