Numbered hats

Cosmin Negruseri
01 august 2012

Andrei Dragus told me an interesting puzzle:

N people stand in a circle and play a game. Someone puts a numbered hat on each person's head. The numbers are from 1 to N and they can repeat. Each person 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.

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.