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.

For the most people to survive by just saying 'white' or 'black' the last person, number 10 in line, should call out the colour of the number 1 in line's hat. Number nine should call out number two's colour and so on. In this way it is guaranteed that the last five people will definately survive and the first five will have a 50-50 chance at surviving. If there were fears that the monster might be suspicious a pre decided order can be arranged so that no. 10 for instance could call no. 3's hat. This will therefore show no logical signalling.

If no. 10 called no. 9's hat, no. 9 called no. 8's hat etc, the group would run into difficulties because if the hat of the person in front of them differed to their own colour, would they save themselves or signal the person immediately in front of them.

If values were allowed to be called out, when calling out the colour, it is possible to save at least 90% of the people. No. 10 calls out no. 9's colour. No. 10 therefore has a 50-50 chance at survival. No. 9, now knowing the colour of the hat on his head sees when that colour occurs again in the row. Say for instance that no. 9 has a black hat and the next person with a black hat is no. 6, no. 9 should call out "Black 6". 6 knows that his hat is black. 8 and 7 know their hats are white. When it is 6's turn to call, he calls out the next black hat again with the no. of that person. In this way every one knows the colour of their hats and at least nine will survive.

If it seems too simple and the monster might find out any mathematical relationship can be applied to the value added. This will therefore make the monster oblivious of the signalling.

Posted by Goldfish on 2003-03-22 23:09:43