# 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...**

Introduction To Word Fit Puzzles

Word fit puzzles are one of those types of puzzle that have a huge range of different names: you might know it as letter fit, or kriss kross, or indeed as criss cross. Whatever you know it as, the rules are the same: place each word into the grid once....*Added: 24 Apr 2015*

Codeword Solving Tool

If you want help with solving codewords, then there are various tips and techniques that you can use, as outlined on other blog entries here at Wordy Puzzle.
However, sometimes if you get completely stuck on a puzzle, then you might want some outside...*Added: 18 Mar 2015*

Novelty Crosswords: Missing Vowel Puzzles

A missing vowel puzzle is a type of crossword variant that, as the name implies, is rather light on vowels!
The puzzle is presented as a normal crossword, but with a novel twist: instead of orthodox clues, all the answers appear under the grid, BUT...*Added: 27 Mar 2015*

Tips On Filling In A Crossword Grid

Writing a crossword is one of those many tasks in life that may seem very easy - until you come to do it! And many don't even think about the grid-filling part, simply the clue writing. Here we look at filling the grid, which must be done before you come...*Added: 03 Apr 2015*

Cryptic Crosswords: Know Your Setter

When you solve cryptic crosswords, one of the best things to do is to follow those in a particular newspaper or major publication. That's because this will enable you to see who sets each puzzle, and over time you will get used to the style of each...*Added: 18 Apr 2015*

Back to Puzzle Blog