There's an obvious generalization of this problem: There are a rather large number of prisoners, each of them seeing the color of the hat of all the following sad fellows bot not their; the hats may be of one of $n$ different colors, and everyone in turn must state the color of his hat, without uttering anything else. If they may devise a strategy in advance, at most $n-1$ prisoners will state the wrong color - needless to say, the rules should say that all of them will be released if at least a certain threshold of answers are correct, otherwise nobody would bother to help the other ones :-)
I was hovever wondering if there is an algorithm that gives a better chance of (global) survival. Any idea?
Answer
Only one person must risk death when using the correct strategy.
You must use the same approach, but instead of binary arithmetic use arithmetic mod $n$.
Before choosing, the prisoners number the colours from 0 to n-1. The first person calculates the sum mod $n$ of colour values for the hats he sees and answers with that value's corresponding colour. He will die with probability $(n-1)/n$, but each other person can calculate his colour and survive.
No comments:
Post a Comment