The Three Colour Hat Guessing Game on Cycle Graphs

Abstract

We study a cooperative game in which each member of a team of N players, wearing coloured hats and situated at the vertices of the cycle graph with N vertices, is guessing their own hat colour merely on the basis of observing the hats worn by their two neighbours without exchanging the information. Each hat can have one of three colours. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colours. We prove that a winning strategy exists if and only if N is divisible by 3 or N = 4. This asymmetric game is an example of relational system using incomplete information about an unpredictable situation, where at least one participant has to act properly.