45
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 28
    $\begingroup$ The last one in the line shouts the color of the all hats of the people in front of him in order before he is killed for cheating. $\endgroup$
    – ratchet freak
    Commented May 20, 2014 at 15:05
  • 7
    $\begingroup$ @ratchetfreak That's a pretty big risk when the entire human population is at stake. $\endgroup$
    – arshajii
    Commented May 20, 2014 at 15:06
  • 5
    $\begingroup$ Nice answers... I would've started cheating by waiting a certain amount of seconds before answering and conveying information to the others in this way ^^ This would even work, if you can only see the hat right in front of you, just wait 10 seconds with your answer if it is green, answer immediately if it is purple :-) $\endgroup$
    – Falco
    Commented Aug 4, 2014 at 14:44
  • 2
    $\begingroup$ @Elgert The accepted answer does not depend on the distribution of hats. The earlier answers tells you if there is odd or even number of hats with a given color. If the earlier answers indicate that the previous answerer saw an even number of purple hats, and you see an odd number of purple hats, do you have enough information to state the color of your hat? $\endgroup$
    – Taemyr
    Commented Oct 9, 2014 at 14:01
  • 3
    $\begingroup$ Do we know who came up with the prisoners-and-hat problem originally? $\endgroup$
    – chx
    Commented Apr 22, 2017 at 4:26

6 Answers 6

Reset to default
46
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ This works perfectly. $\endgroup$
    – Ross Millikan
    Commented May 20, 2014 at 15:32
  • 4
    $\begingroup$ Yup. The first hat call is a parity bit. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented May 21, 2014 at 4:36
  • 2
    $\begingroup$ does the ninth person knows if the tenth survived or not? $\endgroup$
    – libathos
    Commented Oct 3, 2014 at 9:38
  • 3
    $\begingroup$ @krismath Absoultely not; this solution works for any combination of green and purple hats. Assume, e.g., all hats were green except the person second-from-back: <back>GPGGGGGGGG<front>. The first person sees 1 purple hat in front of him and 8 green hats. He says "purple" to indicate an odd number of purple hats (one purple hat). The next person goes and sees an even number of purple hats (zero purple hats), so he knows that his own hat must be the one that made the total purple count odd. All the rest hear the second person announce his purple hat, and they know all their hats are green. $\endgroup$
    – apsillers
    Commented Oct 10, 2014 at 16:31
  • 3
    $\begingroup$ @krismath: If they know that there are 5 purple and 5 green hats, they don't even have to talk to always have 100% chance of rescuing the population. Because the last one will see which one he has, and from then on, everyone does the math. Last has purple, so he sees four purple and five green. Now the second-to-last knows that of his and the eight he sees four are purple and five are green... and so on... $\endgroup$
    – Alexander
    Commented Oct 13, 2014 at 14:12
16
$\begingroup$

Generically, what do you do if there are $c$ colors, and $n$ people? Imagine further the aliens say the following:

You can plan your strategy now, but we are only going to tell you what the colors are going to be (including their hex representation) and how many there are after you are no longer allowed to communicate.

How well can the humans do? It's the same as before, except the human who goes first has a $\frac{1}{c}$ chance of survival.

In advance, the humans use the following strategy:

  1. Each color is assigned a number from $0 \rightarrow c-1$ (this is arbitrary, the humans just have to agree on some numbering).
  2. The human who goes first adds up the colors of all the hats that he sees, and computes the result $\bmod c$.
  3. He then calls out the color required to make the total sum equal to $0 \bmod c$.
  4. Each remaining human can then use the colors called out behind them and the colors they see in front of them to see what the total must be.

This strategy works no matter how many or how few humans there are.

Example: 5 colors, 8 humans. Their hats have color numbers (assume the humans are all facing right, so the first human is the leftmost hat):

32130343
  1. The first human sees 2130343. This adds to $16$. Note $16 \bmod 5 \equiv 1$, so to make the total come out to be $0$, he calls out $4$, because $0 \equiv 4 + 1 \bmod 5$.
  2. The second human sees 130343, and has heard $4$. This adds to $18 \equiv 2 (\bmod 5)$, so he knows he must have color $2$.
  3. The third human sees 30343, and has heard 42. This adds to $19 \equiv 1 (\bmod 5)$, so he must have color $1$.
  4. This process proceeds down the line, and only the first person dies.
Improve this answer
$\endgroup$
10
$\begingroup$

This puzzle has a computer science interpretation¹.

The humans must provide 10 bits of information in total (each hat color is one bit of information). Participant number $k$ (with #0 at the back and #9 at the front) will hear $k$ bits of information from the humans behind him and will see $10-k-1$ bits of information on the heads in front of him. So there's one bit missing.

The person at the back cannot do better than guess at random, since he has no information whatsoever that would indicate his own hat's color. Therefore the strategy should provide information that will help his successors optimally. The amount of information is precisely one bit, which is what the other partipants need.

Assuming that all the participants except poor #0 succeed in calling their own hat's color, participant $k$ will have complete information except for #0's hat color (which is irrelevant) and his own hat color. In other words, he has a bit string with one bit missing. This calls for an error correcting code!

Since the position of the error will be known, a very simple error correcting code is sufficient: a parity bit. Participant #0 calls out (for example) “purple” if he sees an even number of purple hats and “green” otherwise. Each other participant deduces from what he hears and sees whether the number of purple hats other than #0's and his is even or odd, and calls accordingly.

¹ Which, in as much as puzzles belong in a job interview, makes it a little relevant when interviewing for a programming job. The puzzle itself is older than Google. It may well be older than computers, but I don't know its origin.

Improve this answer
$\endgroup$
5
$\begingroup$

Why make it so confusing.

"If I yell my colour, yours is the same."

First guess is 50% chance of success. Yells if it's the same as the hat directly in front, speaks quietly if it's not.

This has the added benefit that if someone stuffs up the count the rest can continue with a 50% chance of sacrificing a single person.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ and they all get killed for cheating $\endgroup$
    – njzk2
    Commented Oct 20, 2014 at 21:37
-1
$\begingroup$

Apologies if its against the spirit of the question (which it may be as they cannot talk to each other during the 'test').

The individuals could tap the shoulder of the person in front as a code; for example left shoulder your wearing a green hat, right shoulder if your hat is purple.

This would only leave the initial person to guess their own hat, ensuring 9/10 survival rate and a 50/50 chance for the first person to guess.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ If you're going to cheat, then why can't person #1 just tap the shoulder of person #0 before he makes his guess? $\endgroup$
    – ThePopMachine
    Commented Oct 6, 2014 at 17:22
  • $\begingroup$ This is not the answer, this is just finding loopholes in the OP's framing of the question, which in the real situation the aliens won't have. $\endgroup$
    – cst1992
    Commented Jan 19, 2016 at 11:14
-2
$\begingroup$

I suppose if the humans were willing to stretch the rules a little bit,

Each guess could contain the color of the hat in front of the person guessing.

So if they knew

Their hat was purple (because of the previous human's guess) and the next in line was a orange, they would guess "Not Orange". If the next in line was purple, they would guess "Purple".

The first guess would be a 50/50 guess, but would give the next human (and so forth) the necessary information to survive.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.