66. How Many Wise Men Can Be Saved?
Ten wise men are forced to stand in a single file line, all facing forward so that each man can see the hats on all the men in front of him but none behind him. A guard then places a hat on every man's head; each hat is either red or blue.
Starting with the man at the back of the line (who sees everyone else's hat) and proceeding forward one by one, each man must loudly say one word—either "red" or "blue"—which is taken as his guess of his own hat colour. If he guesses correctly he lives; if he is wrong he is executed on the spot. Everyone hears every answer as it is given, but no other communication is allowed.
Before the hats are placed the men may confer and agree on any common strategy.
Question: Can they devise a strategy that guarantees all ten men survive? If not, what is the best they can do, and how does the optimal strategy work?
Added 11 January 2011
Hint: Think about what information the last man in the line can communicate using just the single word he is allowed to speak.
Solution:
No strategy can guarantee that all ten men survive. The best possible plan guarantees that nine men live and leaves only the very last man with a 50 % chance of survival.
The agreed strategy is based on parity (even or odd count) of the red hats that the back man can see:
- Beforehand they agree: the first speaker will say "red" if he sees an even number of red hats in front of him and "blue" if he sees an odd number of red hats.
- All other men know this rule. After the first word is spoken, each subsequent man counts the number of red hats he can see in front of him and compares that to the parity announced by the first man and to the answers already given behind him. From those three pieces of information he can deduce with certainty the colour of his own hat and answer correctly.
Consequently, the last nine men are saved with certainty. The very first man, however, had no information about his own hat—he used his single word solely to transmit the parity bit to the others—so his own guess is correct only half the time. No different strategy can do better, because whatever the first man says, at most one bit of information can be conveyed, while two bits would be needed to determine both the colour of his hat and the parity for the rest. Therefore a 100 % survival rate is impossible.
Comments (1)
The wisemen problem involves saving only up to 99 wise men. Can you clarify the solution?
Add a Comment or Suggest an Answer