One hundred programmers

Question:

One hundred programmers are lined up one in front of the other by an evil human resources person such that programmers can see only the programmers in front of them. The HR person puts a red hat or a blue hat on every programmer. The programmers cannot see their own hats, nor can they see the hats of those behind them, but they can see the hats of the people in front of them. The HR person starts with the last programmer in the back and says, “What color is your hat?”

Programmers can answer with only one of two words, red or blue. If the answer does not match the color of the hat on the person’s head, the candidate is dismissed. Then the evil HR person moves on to the next programmer, going from the rear to the front of the row. Programmers in front get to hear the answers of the programmers behind them, but not whether they are dismissed or not. They can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than by what has been specified.

What strategy should the programmers select to guarantee the maximum number of surviving programmers?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: Is the best strategy for every programmer to say the same color, let’s say “red”? Assuming the hats were randomly distributed, half of them would survive. Another strategy calls for every programmer to identify the color of the hat on the head of the programmer immediately in front of him or her. This guarantees the survival of that programmer but does nothing to promote the programmer’s own chances for survival. This strategy also guarantees that at least half survive, plus a little more since chance predicts that some of the programmers would have hats of the same color as the person in front of them, thus sparing them both. In fact, assuming the random distribution of hats, this strategy yields a survival rate of 75 percent. Getting better.

Some candidates might try to game the puzzle by suggesting that the people in the puzzle could agree to give clues to each other by using a certain tone of voice or drawing out the words. One candidate suggested that they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color. Recruiters think this is definitely good and on the correct track. Another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number (red = 1, blue = 0).

But the ideal solution, according to most recruiters, acknowledges that the programmers can say only “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. A good way to get this point across is simply to change the problem slightly by saying “the evil HR person gets to hear their plan beforehand and will thwart it if it is not to the rules.”

But even with the HR person hearing their plan in advance, there is still a way to save almost everyone. We know that the first programmer is never going to have any information about the color of his or her hat so this person cannot be guaranteed to survive. But every other person can be saved with certainty. The programmers simply agree that if the number of red hats that the rear-most person can see is even, then the programmer will say “red.” If the number of red hats that the rear-most person can see is odd, the programmer will say “blue.” This way, programmer number 99 can look ahead and count the red hats. If the sum of red hats is an even number and number 100 said “red,” then 99 must be wearing a blue hat. If they add up to an even number and number 100 said “blue,” signaling an odd number of red hats, number 99 must also be wearing a red hat. Number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on the head of programmer 98.

Even if the evil HR person knows the plan, the person can’t thwart it. The plan doesn’t rely on any specific ordering of the hats. The worst outcome is that the evil HR person will ensure that programmer number 100 is dismissed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s