Source

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.

Problem

$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 his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly?

Solution
Reveal

Assign the $N$ players the tags $0$ through $N-1$. Each player $i$ should add up all the other players' hat numbers, subtract this from $i$, compute the result modulo $N$, and guess that.

Essentially, each player $i$ is guessing that the sum of *all* the hat
numbers will be congruent to $i$ modulo $N$. If this happens, then his
calculation will give his own hat number. Of course, the sum must be
congruent to *some* number $j$ where $0 \leq j \leq N-1,$ so some
player $j$ will guess correctly and will wind up correctly identifying his
hat.