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?