# 100 Hat Riddle Interview Question Solution

Here is the most common set-up of this question the so-called '100 hats riddle':

100 prisoners are given a hat that is either red or blue. They cannot see their own hat. They are lined up in single file in such a way that any given prisoner can see the hats of all prisoners in front of them but not of anyone behind them (or their own, as mentioned, ignore whether this is practical in reality or not).

The grizzly set-up then says that the prison guard will go down the line from the back to front one-by-one asking each prisoner the colour of their hat. If they get it right, they are allowed to live; get it wrong and they are silently killed so no details as to whether they are correct or not are passed down the line. Very pleasant.

So how can you save the maximum number of prisoners? They are allowed to have a meeting beforehand to work out a strategy, but during the process itself they must only say the word 'red' or 'blue' - nothing else can be said at all, they can't even cough.

So what is the strategy they use? That's the interview question. The answer usually given is trading on the fact that it is a fact that there will either be an even number of red hats or an odd number of red hats, no matter how many there are of each colour in total. This fact means all but the final prisoner can be saved if they all think clearly and correctly, although one making a mistake can set up a domino death effect.

The logic is that the final prisoner says 'red' if there are an even number of red hats, or 'blue' if there are an odd number of red hats ahead of him. The person in front can then work out whether this agrees with what they see or not, and thus the colour of their own hat, which they then say out loud. As the number of prisoners is whittled down, prisoners further up the line use the information from other responders to work out their own hat colour (remember only the final prisoner communicates whether he sees an even or odd number of red hats, the rest try to deduce their own colour correctly).

Consider the simplest set-up: three prisoners in the line. Imagine they wear red, blue and red in that order (the last prisoner's colour is never relevant since nobody sees it). Now, the last prisoner can see that there is one red hat ahead - an odd number. Therefore he says 'blue' (and happens to be killed, but that's a 50/50 chance (well, see note below marked *)). Now, prisoner two asks if this agrees with what he sees. Well, it does, since he sees an odd number of red hats ahead (one). This tells him that he must be wearing a blue hat, since if he was wearing a red hat, prisoner three would have said 'red' to signify an even number of red hats ahead. Therefore he says 'blue' and lives.

The last person to respond is person one. He knows that person two answered 'blue', so trivially he must be wearing a red hat to ensure an odd number of red and blue hats, and lives.

Now, that's the answer everyone gives. The logic stays the same as you add more and more people to the line, though everyone must pay careful attention to avoid the domino death effect of making a mistake.

However, the lateral thinking expert here at Wordy Puzzle has come up with a better answer: easier, quicker and therefore much less likely to lead to mistakes. 99 prisoners will live half the time and all 100 the other half of the time, the same as before, however in a practical situation it would actually work (imagine actually having to count 99 hats ahead of you and keep track of the logic as every prisoner talks: mistakes would be made!)

The lateral thinking solution is a lot easier, practical and therefore a much better answer. Note that each prisoner can only say 'red' or 'blue' as their answer: and this is where the lateral thinking comes in - there is no restriction on how they say the word. Here's the new strategy that the prisoners who are good at lateral thinking use, realising that you can communicate more than one thing by saying a single word:

Each prisoner whilst saying red or blue communicates the colour of the hat in front of them by how quickly they say red or blue, apart from the final prisoner: again he simply states the colour of prisoner 99's hat. Then prisoner 99 says the colour of his hat QUICKLY if the colour of the person in front has a hat that is the SAME colour as their own, or SLOWLY if it's a different colour. Thus if prisoner 98 has a blue hat, 99 red and 100 red, then 100 says 'red'. 99 says 'r-e-d' slowly, because 98 has a different colour hat. Therefore 98 knows to say 'blue' with speed based on the colour of 97's hat, and so on down the line. Simple, effective and much less likely to lead to mistakes.

This solution is fully in-keeping with the rules as stated, and that's all that matters in lateral thinking questions: much simpler and actually practical to implement, and stops ridiculous delays between answering: which prison guard is going to wait several minutes for prisoner 100 to answer while he counts hats in the first system. Anyone giving this novel answer who comes up with it afresh should be offered the job immediately!

Finally, a note on '*' above: prisoner 100 is in a very tricky situation, since depending on what he sees, he could easily be tempted to break his promise. Imagine he counts 49 red hats and 50 blue hats ahead of him. He is surely extremely tempted to think this means there are 50 of each colour of hat in total and therefore answer red, killing the other 99 (since he should say blue if there are an odd number of red hats ahead), but saving himself in the process. Equally if there is a huge bias in the numbers, eg 79 red hats and 20 blues ahead, then again he must surely be tempted to answer 'red' since there is clearly far from an equal distribution of hats and each person ahead has a much more likely chance of wearing a red hat to blue, he can reasonably apply that logic to himself to.

Any thoughts or comments on this brainteaser? Do you like questions like this at interviews and think they have value, or would you rather interviewers stuck to experience based 'describe a situation when' questions? We'd love to hear your thoughts on this fascinating topic! Finally, we use 'he' as a shortcut for 'he or she' above, since the sex of the prisoners isn't relevant and 'he' is more succinct.

*Date written: 25 Feb 2016*

**Comment on this post**

You must be logged in to comment - please Register or Login

**Other Blog Posts You Might Find Interesting...**

Cryptic Crossword Anagram Indicators

When solving a cryptic crossword one thing you can be sure of is that there will be some anagram clues, or partial anagram clues, in the solving mix.
Some cryptic crosswords have over 50% of the clues containing anagrams in some form, whilst even the...*Added: 16 Apr 2015*

Solving & Lit Clues In Cryptic Crosswords

When you are solving cryptic crosswords, most of the clue types that you come across are fairly intuitive: for instance a double definition clue fairly obviously involves two definitions that lead to the same answer. And an anagram clue, sure enough,...*Added: 11 Apr 2015*

Wordwheel Player Update

We hope you are all enjoying playing the great range of puzzles we have available online here at Wordy Puzzle.
We just wanted to let you know that we have implemented the most common piece of feedback we have received, which is to do with the...*Added: 28 Jul 2015*

How To Solve Anagram Clues

Solving anagram clues is different for quick and cryptic crosswords. With quick crosswords, the anagram is always indicated, either by (anag) or (anagram) written after the clue.
In contrast, with cryptic crosswords, it is never quite clear what the...*Added: 21 Mar 2015*

Tips On Writing Crossword Clues

Writing crossword clues is a difficult art form, and there is no doubt that lots of practice is essential to getting it right. It is also worth noting right from the start that the style and balance of clues you write will depend very much on the type of...*Added: 04 Apr 2015*

Back to Puzzle Blog