We analyze the following general version of the deterministic Hats game. Several sages wearing colored hats occupy the vertices of a graph. Each sage can have a hat of one of k colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbors without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors.We present an example of a planar graph for which the sages win for k = 14. We also give an easy proof of the theorem about the Hats game on “windmill†graphs.
展开▼
