# Of men and hats

There's an obvious generalization of this problem: There are a rather large number of prisoners, each of them seeing the color of the hat of all the following sad fellows bot not their; the hats may be of one of $n$ different colors, and everyone in turn must state the color of his hat, without uttering anything else. If they may devise a strategy in advance, at most $n-1$ prisoners will state the wrong color - needless to say, the rules should say that all of them will be released if at least a certain threshold of answers are correct, otherwise nobody would bother to help the other ones :-)

I was hovever wondering if there is an algorithm that gives a better chance of (global) survival. Any idea?

• possible duplicate of Hats and Aliens Commented Mar 13, 2015 at 17:24
• It's a generalization of Hats and Aliens but durron597's answer to that question is for the general case. He should post the answer here so that it will receive attention and review for this general case. Commented Mar 13, 2015 at 18:26
• @Len this question is a duplicate of Hats and Aliens and should be closed. I am not going to copy paste an answer as it is against Stack Exchange policy. Hats and Aliens was asked much earlier and has more views and upvotes. Commented Mar 14, 2015 at 13:50
• "If they may devise a strategy in advance, at most n−1 prisoners will state the wrong color " . Which strategy would have led to at most n-1 prisoners getting it wrong ? I cannot figure out what strategy you were thinking of. Commented Dec 8, 2020 at 23:53

You must use the same approach, but instead of binary arithmetic use arithmetic mod $n$.
Before choosing, the prisoners number the colours from 0 to n-1. The first person calculates the sum mod $n$ of colour values for the hats he sees and answers with that value's corresponding colour. He will die with probability $(n-1)/n$, but each other person can calculate his colour and survive.