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
Back to Puzzle Blog