Determining the Number of One Hat


I got this problem from Rustan Leino, who was told it by Clark Barrett, who got it from his father. It may sound reminiscent of the Three Hat Colors problem, but it's different in many ways.

I solved it and wrote up my solution.


$N$ people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first $N$ natural numbers is written. There may be duplicate hat numbers. For example, for $N=3,$ the 3 team members may get hats labeled 2, 0, 2. Each person can see the numbers written on the others' hats, but does not know the number written on their own hat. Every person then simultaneously guesses the number of their own hat. What strategy can the team follow to make sure that at least one person on the team guesses their hat number correctly?

Solution     Reveal