猜帽子问题

Source: An exercise class of Theoretical Computer Science

Description:
There are n people in a room, everyone wears a hat, the color of which could be red, green, or blue, randomly. Each guy can see all the hats except his own. Now there is a spectator coming into the room and asking each of the n guys in private, "which color of hats do you think is on your head?"
Once the n guys are in the hats, their only information is the colors of other guys' hats, and they can do nothing but answer the spectator's question, and of course their answer will not be heard by the other guys. However, before the experiment starts, the n guys can figure out a strategy. What they care is the probability that all of the n guys answer the spectator correctly.

Now your question comes, what strategy should those guys take to make the probability maximal?



Solution:
We label each color with a number of 0,1,or 2, say, red is 0, green is 1, blue is 2. Each guy summarizes the numbers corresponding to the colors he can see, Let S be the sum. This guy will choose number x to be his answer, where x must satisfy that S+x=0 (mod 3).

Obviously, if all of the n guys are using this strategy, then the probability that they all give correct answer is 1/3, because if one of those guys is right, then all of the n guys are right.


Remark:
Actually there is another version of this problem. This version says the n guys stands in a queue and each guy can only see his preceding guys. The spectator ask the guys from the back of the queue to the front, and each guys answer can be heard by his successor. The question of the problem is the same with the original one.
We can use an similar (almost the same) strategy to solve this version of problem. If you are interested in it, think about it.