Imre Leader via Paul Cook. Two two-hour thinking sessions got me not very far with this, and then the following morning I woke up with the answer fully formed in my mind. I felt a bit robbed. Like I'd been told the answer while asleep. Stick at it. Those who like this sort of thing will like this very much.
There are six people.
For each person, you roll a dice, and write the number on the hat.
They all close their eyes, and you put on each person his hat.
They all open their eyes. Without any communication whatsoever and without looking at their own hat they have to guess the number on their own hat.
If any one of them gets it right then you give them all gold and elsewise you shoot them, or something. You know the score with psychotic maths problems.
Anyway the guys are conferring before the game. What is their plan?
In general choose n, a natural number. n people, n hats, n-sided dice, n pots of gold, n bullets.