A challenge is given to 100 people. A hat will be placed on each of their heads, and each hat will have an integer between 1 and 100 written on it (numbers can repeat). Every person will be able to see the hats of the other 99, but not his own. After that, everyone will have to guess what is the number on their hat (without others hearing). If at least one person guesses correctly, they will be awarded 1 million dollars. What strategy should the people come up with in order to optimize their chance of winning?
Label the people with numbers 1, 2, 3, ... , 100. A strategy which ensures 100% success is the following:
Person X should sum the numbers on the hats of the other 99 people, then subtract the result from X, and take the residue modulo 100 of the answer (say "100" if the residue is 0).
This way if the sum of the numbers on all hats has residue R when divided by 100, then person R will guess correctly the number on his hat.