Prasad brought work to a halt earlier this week by issuing the following little conundrum. One indepdenent fair 6-sided die is rolled for each of n people. Each person’s number is written on a card and stuck on their head so that they can see everyone else’s number but their own. The people are not allowed to communicate after the numbers are assigned, and from just viewing the others’ numbers they must guess their own. They can come up with any rule that they like for doing this.
What rule should you choose to that is the probability that all of them guess correctly is maximized, and what is that probability?
This is a variation on the “colored hats game,” but the criterion you want to maximize is slightly different than in some instances of the game.
An Ergodic Walk 
Interesting. My guess for the rule would be “Choose the number that occurs the fewest times on the other people’s cards” and institute a tiebreaking mechanism that’s evenly distributed among the people. I don’t have the patience to calculate the expected value though…
The naive strategy is that everyone guesses randomly, independently of the other people’s numbers — this gives a (1/6)n chance of working, whereas the optimal strategy is significantly better than that.
The scheme you suggest will likely not work so well for the following reason : with high probability, n/6 people will have each number, and one persons trying to equalize the distribution of numbers will not make enough of an effect.
That being said, your idea is heading in the generally correct direction…
Here is my first guess. Every person guesses the number that would make the sum of all numbers to be a multiple of 6. That gives a probability of winning of 1/6. That has to be the best we can do, since player 1 can never design a strategy that will allow him (independently of what the others do) to guess his own number right with probability better than 1/6.
Really cute problem.
I have failed as an applied mathematician.
Fortunately, I’m not trying to be one.
This puzzle underlies several (negative) results on error amplification via parallel repetition in cryptography, the most recent being “Krzystof Pietrzak and Douglas Wikstrom, Parallel repetition of computationally sound protocols revisited, Theory of Cryptography Conference, 2007.”