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 participants 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.}

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.}

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.}

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 participants 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.}