Can everyone be saved?
A king has captured 100 thieves who were attempting to steal his crown jewels. However, he also admires their ability to almost pass through security. He decides to challenge them.
He lines up the thieves into a straight line and puts either a red or blue hat on them. The thieves can only see the colours of the hats in front of them. (e.g. Thief 1 can see everyone else's hats, Thief 2 can see everyone hats except for himself and Prisoner 1, etc.). Once lined up, they must not communicate amongst themselves. Nor may they attempt to look behind them or remove their own hat. The thieves will be able to hear the answers from all those behind them.
The king starts with the first thief (who is at the back of the line) and asks, "What color is your hat?". The thief is only allowed to answer 'red' or 'blue,' nothing more. If the answer is incorrect then the thief will be silently killed. If the answer is correct then the thief may live but must remain absolutely silent.
The king then moves on to the next thief and repeats the question.
The king makes it clear that if anyone breaks the rules then all the thieves will die, then allows the thieves to consult before lining them up. The king listens in while the thieves consult each other to make sure they don't devise a plan to cheat. To communicate anything more than their guess of red or blue by coughing or shuffling would be breaking the rules.
What is the maximum number of thieves that can be guaranteed to be saved?
The answer is 99.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
The first two paragraphs are redundant to the actual solution. You should explain why there are there.
Note that you've only shown that 99 can be achieved using your method. You have not shown that this is indeed the maximum that can be achieved using every possible method.
You can save about 50% by having everyone guess randomly.
You can save 50% or more if every even person agrees to call out the color of the hat in front of them. That way the person in front knows what color their hat is, and if the person behind also has the same colored hat then both will survive.
So how can 99 people be saved? The first thief counts all the red hats he can see ( Q ) and then answers "blue" if the number is odd or "red" if the number is even. Each subsequent thief keeps track of the number of red hats known to have been saved from behind ( X ), and counts the number of red hats in front ( Y ).
If Q was even, and if X & Y are either both even or are both odd, then the thief would answer blue. Otherwise the thief would answer red.
If Q was odd, and if X & Y are either both even or are both odd, then the thief would answer red. Otherwise the thief would answer blue.
Furthermore, there can be any number of red hats.Therefore, at most, one thief dies for answering incorrectly.