Some facts about Google:
- If you work there you get delicious free food
- Your commute is free
- You can regularly take your dog into work
- They have allotments for employees
- Free yoga and gyms
- Their interview questions are stupidly difficult
Which to an extent makes perfect sense when there’s so many perks to your job and you’re also pretty much responsible for running the internet, but seriously, this riddle is ridiculous.
Here’s the riddle that’s regularly thrown over to interviewees at the company:
The 100 Hat Riddle
100 prisoners are lined up by an executioner, who places a red or blue hat upon each of their heads.
The prisoners can see the hats of the people lined up in front of them, but they cannot look at the hats behind them, or at their own.
Starting at the back of the line, the executioner asks the last prisoner to state the colour of his hat.
In order to live, the prisoner must answer correctly. If he doesn’t, he is killed ‘instantly and silently.’
This means that the other prisoners will hear the answer, but will not know whether or not it was correct.
The night before the line-up, the prisoners can discuss a strategy to help them survive. What should they do?
Give up? Here’s the solution...
The best solution will present a situation where 99 of the prisoners can be saved with 100 percent certainty, while the final prisoner will have a 50/50 chance of survival.
To ensure this, the prisoners must agree upon a communication protocol: The first prisoner to speak will say blue, if the number of blue hats he sees in front of him is even or ‘red’ if the number is odd.
Using this information, the other prisoners can figure out their own hat colours based on the hats they see in front of them, and the responses they’ve heard behind.
In this case, everyone except the first prisoner will definitely answer correctly.
Here’s a longer breakdown
Let’s pretend there’s only 5 people involved
- Person 1 - Follows the rule 'if he sees an odd number of red hats he calls out red, if he sees an even number of red hats he calls out blue.' he calls out blue because he sees an even number of red hats and dies.
- Person 2 - Knows that including himself there’s an even number of red hats. If he looks forward and can also see an even number of red hats. This means he is wearing a blue hat. Had he been wearing a red hat then the person behind him would have seen 3, an odd number.
- Person 3 - Knows they started with an even number of red hats and that nobody other than (possibly) the first person has declared themselves to be wearing a red hat, so including himself there are an even number of red hats. He looks forward and can see one red hat, an odd number. That this has changed between him and the people in front of him means he is wearing a red hat.
- Person 4 - Knows that to start there were an even number of red hats and nobody has been killed other than the first person. So including himself there is an odd number of red hats. He looks forward and can zero (an even number,) of red hats. That this has changed between including and excluding him means he is wearing a red hat.
- Person 5 - Knows that to start there were an even number of red hats. He knows that two have gone. So including himself there is an even number of red hats. He looks forward and can see zero (an even number,) of red hats. Meaning he is wearing a blue hat.
Make sense? Oh, we give up.