There is an island with 10 inhabitants. One day a monster comes and says that he intends to eat every one of them but will give them a chance to survive in the following way:

In the morning, the monster will line up all the people - single file so that the last person sees the remaining 9, the next person sees the remaining 8, and so on until the first person that obviously sees no one in front of himself. The monster will then place black or white hats on their heads randomly (they can be all white, all black or any combination thereof). The monster will offer each person starting with the last one (who sees everyone else's hats) to guess the color of his/her own hat. The answer can only be one word: "white" or "black". The monster will eat him on the spot if he guessed wrong, and will leave him alive if he guessed right. All the remaining people will hear both the guess and the outcome of the guess. The monster will then go on to the next to last person (who only sees 8 people), and so on until the end. The monster gives them the whole night to think.

The Task:

Devise the optimal strategy that these poor natives could use to maximize their survival rate.

Assumptions:

1. All the 10 people can easily understand your strategy, and will execute it with perfect precision.
2. If the monster suspects that any of the people are giving away information to any of the remaining team members by intonation of words when answering, or any other signs, or by touch, he will eat everyone.
3. The only allowed response is a short, unemotional "white" or "black".
4. Having said that, I will add that you can put any value you like into each of these words.

The last person (the first to guess) should guess the same color as the person in front of him. This will leave him with a 50% chance of survival, but also enable the person in front of him, who is the next guesser, to guess that same color, assuring his safety.

The next person forward repeats the same strategy as the first guesser, guessing the same color he sees immediately ahead of him. Then that person guesses the same. This whole pairing continues so that 5 people have used their guess to give clues to 5 other people who use those clues to save themselves.

This is the best that can be done, as each guess can be used to signal one bit of information, or it can use up one bit of information in saving the guesser, so there's no way one guesser can save more than one other guesser.

This increases the expected survival rate from 50% from random guesses, to 75%, as 5 islanders will be assured of survival while each of the remaining 5 still has a 50% chance.

To further throw off the monster, the choice could be to guess the opposite color from the one just in front of the guesser, or some more complicated pre-arranged scheme such as alternating same and opposite. The people would have to decide how much simplicity should be traded off for avoiding the monster's suspicions.

Posted by Charlie on 2003-03-21 08:02:16