Here's a neat little puzzle taken from a Google interview question:
10 humans are abducted by aliens; each represents 10% of the entire human population. The aliens give each abductee either a purple hat or a green hat. The 10 are lined up in a single file line, each facing forward, such that the last person can see the remaining 9's hats, the second to last person can see the remaining 8's hats and so on. No one can see his or her own hat.
The aliens then proceed, starting from the last person, to ask each of the abductees what the color of their hat is. If they guess correctly, they and the 10% of the human population they represent survives; if not, the opposite happens.
Assuming the abductees are given a chance to develop a strategy before they are lined up and questioned: what is the optimal strategy they can utilize (i.e. the one with the highest expected number of survivals)?
During the questioning, the abductees are not allowed to say anything besides their guess for the color of their hat when it is their turn.
Hint:
The optimal strategy will always ensure 9 survivals, and will have a 50% chance of the 10th survival.
Answer
I think this would work? Sorry if it's confusing. I sort of confused myself when I came to this conclusion.
The first guy would count the number of hats before him of a particular color... like, I dunno, I guess purple? And if the count of purple hats is odd, then he would say that his hat is purple. But if the count of purple hats is even, he'd say his hat was green.
So the next guy should then be able to determine the color of his hat by:
The remaining hats. So if the questioning went:
Alien: What color is your hat?
10th person: Purple.
Then the 9th person would look ahead and:
Count the number of purple hats. If it's an odd number, he has a green hat. If it's an even number, his hat is purple. So on and so forth. They just need to remember the "number" of purple hats.
But the first guy has no way of knowing his own hat color, so he's got a 50/50 chance of dying either way.
If anyone has trouble understanding this, a visual explanation can be found here:
https://www.youtube.com/watch?v=N5vJSNXPEwA
No comments:
Post a Comment