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.

I'm gonna show how 9 people can be saved for sure! Let's suppose that 0 stands for white hat and 1 stands for black hat. Then, the first person adds all the numbers in front of him and says "0" if the sum is even, and "1" if it's odd. Now, the second person hears what the first one says, knowing the parity of the sum of his number, plus the ones in front of him. But by seeing the people in fornt of him, he knows the parity of their sum. If both parities coincide, he has a 0, if else, he has a 1. Continuing like this, every person knows: the parity of the sum of everyone starting from the second person (that's what the first one said), the number of everyone behind him (he hears what they say), and the parity of the sum of the people next to him (by seeing them). Knowing these 3 things, a person knows his number, by doing the following: knowing p, the parity of everyone (told by the first person), he substracts 0 if the sum of the numbers of everyone behind him (excluding the first person) is even, and 1 if it's odd. Doing this, we obtain a parity q. Then, the person sums the numbers in front of him (we call this f). He then subtracts 0 from q, if f is even and 1 if it's odd. Now this new number obtained is either 1 or 0. Then, the person says it, and that's his number...
This way, nine people survive for sure, and the first one could also save himself with a little luck...

Posted by Fernando on 2003-03-24 17:56:09