Numbered hats

Cosmin Negruseri
01 august 2012

Andrei Dragus told me an interesting puzzle:

N people play the following game. They stand in a circle. Someone puts a numbered hat on each person's head. The numbers are from 1 to N and they can repeat. Each person can't see the number on his own hat but can see the numbers on all the other N - 1 hats. Each person tries to guess the number on his own hat. If one of them guesses correctly they've won the game. They all say their guess at the same time. Communication occurs before the hats are placed.

1. Prove that the N people can agree on a strategy beforehand such that they can win the game for any hat configuration.

2. Prove that if one of the N people sees just N-2 of the other hats then there isn't any perfect strategy.

Let's discuss the solution in the comment section.