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?

The strategy

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.

Why it works

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 their calculation will give their 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 their hat.