Use common-sense reasoning to crack this tricky puzzle often considered impossible to solve
100 prisoners with black or white hats lined up by a jailer. Prisoners can't see own hat color, but must guess correctly to survive when questioned. How?
The Mind-bending 100 Hats Riddle—A Hard to Solve Classic Logic Puzzle
A jailer in-charge of 100 prisoners is under pressure to empty his jail of the prisoners one way or the other because of rising costs. So he told the prisoners, he will line up the 100 prisoners in a single file. A black or white hat at random will be placed on every head after blindfolding them. When the blindfold is removed, they won't see their own hat but would see all the hats in front of them. Starting from the back, each prisoner must guess their hat color when asked by the jailer. They can only say "black" or "white" in answer to be free if correct. Those failing will be executed instantly.
The jailer will start from the last person, moving one by one to the person standing first in the queue. They can discuss freely among themselves on what they can do. They have only one hour time. As help in their discussions, the jailer gave them a sheaf of white papers, a timepiece and a cardboard box. Can they devise a strategy to maximize the number of survivors?
Assume, all prisoners are capable of logical reasoning ability needed to follow the strategy perfectly.
Time for you to answer with supporting reason is 1 hour, same as the prisoners.
Hint: Start thought experiments and refine strategies to discover the only foolproof way, following step-by-step rigorous reasoning.
The 100 Hats Riddle Solution by Rigorous Common-sense Logical Reasoning
Step 1: Initial thought experiment with a simpler problem set of three prisoners
Think, what can be a feasible strategy taking the simplest case of 3 prisoners.
Possibilities with three prisoners:
- Third prisoner at the back can see the colors of the two hats in front.
- A reasonable strategy considered: if the third prisoner finds both hats in front same color, he will shout out his answer as White, otherwise he will shout Black. Both prisoners in front will hear him shout. By his shout he passes on the key message of hat colors he sees in front to all other prisoners.
- Being the last person at the back, his chance of survival is 50%, because from only the information of hat colors in front he won't be able to guess his own hat color—he has to make one random guess out of two possible hat colors. He plays a sacrificing role.
Case 1: Third prisoner shouted White: The second prisoner shouts his hat color same as the color of first prisoner's hat in answer. He will be free as will be the first prisoner using a logical deduction based on earlier shouts.
Case 2: Third prisoner shouts Black: The second prisoner will shout his hat color as opposite to the hat color of the first prisoner in answer. Here also the second and the first prisoner will survive.
Question raised: But, will this strategy work for 4 persons or 5?
Answer: It is easy to realize, when number of prisoners is more than 3, the strategy of using the key message based on same or different hat colors in front will fail with low chances of survival.
Insight: Sameness or difference in hat color can't be the way to the successful strategy. A unique property about the hat colors any prisoner sees in front is needed.
Step 2: What can be a key unique property of hats a prisoner sees in front for the successful strategy?
- First genuine progress achieved through reason: Apart from the color of hats that the second to the 100th person sees in front can only be the number of colored hats.
A promising chain of logic towards success ensues:
- Fact: The prisoners in front must get useful information from the last prisoner, the prisoner 100 at the start, but always from the last prisoner.
- Fact: With no help from anyone's answer, the chance of survival of the prisoner 100 would be 50%. Like tossing an unbiased coin, he has to choose either White or Black as an answer randomly.
- Realization of Uniform strategy for all: The strategy to be successful, each of the prisoners must answer following the same strategy known and agreed among all—it must be a collaborative team effort. Otherwise, randomness and chaos will reign, minimizing chances of successful survival of the group.
- Realization of the significance of two answer values: As the answer can only be Black or White, the property of hats based on which the answer to be given must also have only two potential values.
- Realization: Number of hat colors key factor: As the sameness or difference of hat colors cannot be the key aspect of the hat, the number of black or white hat colors in front must decide what to answer.
- Conclusion: Key property of number of hat colors in front discovered: The only property of numbers of White or Black hat color each prisoner can see in front is:
- Whether the number is odd or even. This is the only property of all integer numbers having exactly two values. And, this property applies to all prisoners in the same way.
- One prisoner remembered hearing the term Parity to represent the property of odd or evenness in integers. From then on they decided to call the in-front number of a specific color of hat being odd or even as Parity.
Step 3: Identifying the Basic Information to be used by each prisoner—Strategy
It was decided as a strategy to be followed by all:
- The prisoner 100 will count the number of White hats (it may be Black also with similar result) in front. If this Parity is odd his answer will be Black. If it is even, his answer will be White. This hidden code will be the critical input information passed down the line to the other prisoners by his answering shout.
- Each will refer and use to this as just Parity.
- Parity of a prisoner will show with certainty whether he sees an even or odd number of White hats.
Realizing at this early stage, the critical importance of avoiding random approaches, they right away decided to find out what must be known by any prisoner when asked the deadly question to guess his own hat color correctly.
Step 4: Focusing on the core question—What Must be Known by Each Prisoner When His Turn to Answer Comes
Realization that made sense: To guess own hat color correctly, any prisoner must know when his turn comes,
- The Parity of the prisoner just behind him who answered last.
- He will know his own Parity from the number of White hats he sees in front.
- Based on these two Parities, he will guess his hat color with full certainty.
- Knowing only the Parity of prisoner 100 (passed on as a message to all by his shout) and the Black or White answer of his immediate predecessor won't be enough.
The prisoners went on to check the correctness of their key assumption for any prisoner:
A. Parity of the prisoner just behind ODD:
- The prisoner’s own Parity ODD,
- His hat color contributed 0 to his predecessor's odd Parity keeping the parity of White hats unchanged for him—his predecessor didn't see a White on his own head,
- Conclusion: His own color of hat must be Black.
- The prisoner’s own Parity EVEN,
- This means he must reduce 1 from the odd Parity of his predecessor to get his own Parity as even changing its state from odd to even for him.
- Conclusion: His hat color must be White, his Parity one White hat less than the Parity of the prisoner just behind him.
B. Parity of the prisoner just behind EVEN:
- The prisoner’s own Parity ODD,
- His color of hat must have reduced 1 from his predecessor's even Parity changing it to odd for him.
- Conclusion: His color of hat must be White.
- The prisoner’s own Parity EVEN,
- It means his color of hat contributed 0 to his predecessor's even Parity keeping its state unchanged.
- Conclusion: Parity contribution 0 means his color of hat must be Black.
Confirmed Key Conclusion: With the knowledge of the Parity of his immediate predecessor, any prisoner will correctly guess his own color of hat with certainty.
Step 5: But, how could any prisoner know the parity of his immediate predecessor?
Chain of reasoning:
- Prisoner 99 will know the Parity of the prisoner 100 from his agreed and strategic coded answer. This coded message will be known to all others by the shout of the prisoner 100. His answer of White or Black will be correct with 100% certainty.
- Prisoner 98 will correctly deduce the Parity of his predecessor by
- Subtracting 0 for Black and 1 for White in his predecessor's answer from the coded Parity of prisoner 100.
- Prisoner 97 will correctly deduce the Parity of his predecessor using the answer of his predecessor AND following the logic same as his predecessor prisoner 98 in his deduction of Parity of prisoner 99.
They wondered:
For correctly guessing his own color of hat, would it be necessary for each prisoner to remember what each prisoner behind him answered! That would create a large memory and deduction load for each.
Step 6: Discovery of the most efficient way to deduce one's own color of hat
They went through the ways of correct answer by prisoner 99, prisoner 98 and prisoner 97 and found an action common for each:
- Before answering Black or White, prisoner 99 knew the Parity of the prisoner 100.
- By his answering shout, effectively he
- updated his own Parity,
- let all the prisoners down the line know his own Parity.
- As soon as prisoner 99 answered, prisoner 98 knew the Parity of prisoner 99 and so could guess correctly. By his answering shout he let all after him know his own Parity.
- Prisoner 97 needed to remember only the Parity of prisoner 98 to guess correctly, which he came to know just when the prisoner shouted his answer.
The prisoners were relieved to know
To correctly guess his hat color, each of them need to remember the updated Parity of the last prisoner who answered—nothing more.
Following this overall strategy, they decided, 99 of them could certainly be free except prisoner 100 who stood a 50% chance of survival.
Step 7: Trial run of the strategy for maximum survival for 7 prisoners
Being fast thinkers with no random straying thoughts, they had some time. So, they decided to put the strategy for success through a trial run for 7 prisoners, a fairly representative number.
With the help of the paper and pencil, they tested out various combinations of Black and White hats. A combination of Black and White hats tested is shown below.
For each combination, their strategy worked like a charm till they stood confused when they chose all Black hats for 7 prisoners.
What should the prisoner 7 at the back would shout as his coded message? What would be his Parity—odd or even!
Step 8: Discovering Parity of 0 as even—Ultimate Strategy for Maximum Survival
Again, simple logic and basic concepts came to their rescue. One of them pointed out—0 is less than 1, an odd number, by 1. So it must even.
Step 9: Ultimate Strategy for Maximum Survival
- Prisoner 100 will shout White if he sees an even number of White hats, including zero, in front. Otherwise, if he sees an odd number of White hats he will shout Black.
- This first answering shout will inform all 99 prisoners in front, the Parity of prisoner 100 in coded message.
- It will act as an anchor message on which the success of the entire strategy will wholly depend.
- The chance of survival of prisoner 100 will be exactly 50%.
- His role will be to sacrifice himself knowingly to save others.
- Knowing the Parity of prisoner 100, and the number of White he sees in front including zero, prisoner 99 will deduce his own color of hat correctly.
- His correct answering shout will inform all the rest about his Parity of White hats.
- Each prisoner will remember only the updated Parity of the last prisoner who answered.
- By this simple all-agreed strategy and teamwork, all 99 prisoners except the prisoner 100 will ensure their freedom.
Someone raised the question of erroneous answer at any stage.
Being thorough, they considered this, though unlikely, situation with seriousness.
- If any prisoner down the line makes an error in counting or failing to update the Parity of the last prisoner who answered, he will be instantly executed. By the act of his execution, all the rest will deduce the correct Parity of the executed man.
- If the prisoner 100 makes an error, the whole strategy will break down and all subsequent prisoners will stand a chance of 50% to survive.
- Solution: They knew, there can't be any 100% error-free human system. But chances of error could be reduced by the method of each prisoner triple-checking before shouting his answer.
Step 10: A Question of Justice and Morality
Though the prisoners knew they successfully created the maximum survival strategy, they felt depressed unable to confront the question—who will assume the position of prisoner 100, the self-sacrificing position!
Having covered this much, they could also solve the problem.
In 100 similar small pieces of paper, they wrote the numbers 1 to 100 and put all into the box so thoughtfully provided by the jailer (hats off to him!). Shook the box thoroughly and closed the lid.
One by one, each opened the lid of the box and drew one piece of paper—his ultimate position number.
The story doesn't end here.
It is true:
God feels kindness towards those with intelligence, basic concepts, ability to use reason when facing emergency and above all, who work as a collective team wanting good for all others in the team.
That's why, the prisoner 100 also made a correct answer when conveying the coded message to all others—all 100 prisoners earned their freedom.
All they needed to know was the odd and even number concept and the ability to carry out rigorous common-sense reasoning as a team.
Problem solving abilities, concepts and techniques used in solving the 100 hats riddle
- Rigorous Common-sense reasoning: It is possible that even a common person can carry out common-sense based reasoning. But the trick lies in how rigorously one uses her reasoning.
- Thought experiments: This concept is often used in work environments to design and test prototypes before last production.
- Solve a simpler problem: In academia and work environments, this is a well-known and often used technique for solving complex problems by forming a simpler problem without ignoring the essentials of the more complex actual problem.
- Odd number and even number concept: Even a child knows the concept that integer numbers can be odd or even. But it not so well-known that the number 0 is technically even. Without knowing this technicality, rigorous common-sense reasoning could help discover this property.
- Thoroughness in thinking: This is the most ignored concept and technique in problem solving that results in critical gaps in a solution. I have identified this important technique as the Principle of exhaustivity. The prisoners were so thorough in their approach, they even considered the dilemma of choosing who will assume the sacrificial role of the prisoner 100 objectively.
- Triple check of the strategy—Rehearsal: This is equivalent to the widely used practice of rehearsal before any stage performance, revisions before exams or practice before important sports events.
- Teamwork: Last but not the least was the discovering and following the strategy as a team, collectively. This improves the chances of success immensely and brings out the best from each team member.
Last Words
- The exceptional group of prisoners can be any group of 100 common persons with the basic reasoning ability and knowledge of the most basic kind.
- The ultimate strategy arrived at was so simple that any group of 100 such persons should be able to deduce and follow the strategy in a team without any difficulty.
- This solution will apply for even as large a number as 1000 prisoners. Only problem will be how to communicate each prisoner's answer to every other prisoner!
- With advanced communication facilities available today, that could easily be taken care of by the jailer.
Want to Know More?
Appreciate the different solutions to this classic mind-bending logic puzzle sometimes considered as impossible to solve.
- 100 Prisoners with Red or Black Hats - geeksforgeeks: Any difference you notice? This attains the first position in the Google search. Look for thorough correctness.
- Riddle of the Week #16: The Puzzle of 100 Hats - popular mechanics: This is a well-regarded website for such puzzle. So go through the solution to appreciate how the solution unfolded. Look for thorough correctness. Here the puzzle has been consider as hard to solve.
- Solution to 100-Hat Puzzle - New York Times: The 100 hats puzzle is so highly regarded that it attracted attention of even the New York Times. Look for thorough correctness.
More puzzles to enjoy
From our large collection of interesting puzzles enjoy: Maze puzzles, Riddles, Inventive puzzles, Paradoxes, Mathematical puzzles, Logic puzzles, Number lock puzzles, Missing number puzzles, River crossing puzzles, Ball weighing puzzles and Matchstick puzzles.
You may also look at the full collection of puzzles at one place in the Challenging brain teasers with solutions: Long list.
Enjoy puzzle solving while learning problem solving techniques.