I dont know if you have seen this one, it is a generalisation of a classical brainteaserSuppose you have N prisoners, sentenced to death (tomorrow). But the king (who likes brainteasers) gives them a last chance: Tomorrow, every prisoner will have a colored hat, and there is M possible colors. Every prisoner will see all the others and their hats, but he will not have the right to talk with them or to see his own hat. The N prisoners will be together in the same auditorium, and will pass alternately ahead the king. Every prisoner will have to guess the color of his own hat: if it is right, he will be pardoned, otherwise he will be killed.The prisoners can meet today and decide a strategy. What is the best strategy to minimise the number of killed prisoners?

Nobody?Hint: The solution is: N-1 prisonners can be free!

I think this strategy might work:First the prisoners number the colors 1,2,....,M.Then prisoner n (just anybody will do) looks at all the other hats and does the following thing:for every prisoner i (i=1,2,...,n-1) he looks at his hat, and the adds the number of the color of this hat to the grand total X.So he gets the number X as sum of n-1 numbers.He then finds Y = X mod M. He goes up to the kind and says the color corresponding to number Y.Doesn't matter if he gets killed or not, the important thing is everyone else can survive now.Prisoners 1,2,....,n-1 go in order of their indexes.Then for prisoner i (i=1,2,...,n-1) he knows the total Y_{i} of numbers of colors of his hat and all hats of remaining prisoners (i, i+1,...,n-1), because he can keep subtracting z_{i} from Y-{i-1} (in terms of mod M, where Y=Y_{1}) and z_{i} is number of color of hat of prisoner who just went before him.He also knows total T_{i} of numbers of hats of remaining prisoners (i+1,...,n-1), NOT including prisoner i, by just adding all numbers of colors of hats he sees.Then Y_{i}-T_{i} mod M is number of color of prisoner i. But this number Y_{i}-T_{i} allows prisoner i to find what color his hat is (from the assigning of "color numbers" in the beginning). So prisoner i gets the right color and survives.So all prisoners 1,2,...,n-1 survive. This is optimal because first prisoner to go up has no way of knowing his hat color so there is no guarantee all n prisoners will survive.

That's it!

Here's a variation. Try with randomized sequences. Prisoners don't walk one by one. One of them is selected randomly and asked to guess What now?

Also your solution has an anomly.Consider only 10 prisoners.3 colors of hats. Red, Green, Blue (RGB)The prisoner n (who is asked) has a red hat....and all others 3 + 3 + 3 have 3R , 3B , 3G hatsso total number = 3*1+3*2 + 3*3 = 18 (assuming we order RGB as 1,2,3)18 mod M = 18 Mod 3 = 0So what will he say...just walk away??? or be quiet!

anyway works with 0,1,2

My favourite hat problem:There are a countably infinite number of prisoners, arranged in a line. Each prisoner is given a black or white hat. They can see all the hats in front of them, but not their own hat or hats behins them. They simultaneously announce there hat colours. Before the guess, they can confer on strategy. (The usual rules apply e.g. any cheating resulting in death for everyone.)What strategy ensures only a finite number dies?

Is the line infinite in both directions? ie when a prisoner looks at the hats in front of him, can he see a finite or infinte number?Not sure the answer helps anyway. If the prisoners have to guess the colour of their hats simultaneously, all they can go on is the colour of the hats in front of them (ie they are not able to use any information from other people's guesses). For only a finite number or prisoners to die, they must be able to correctly guess the colour of their own hat almost surely. I can't see how that can be possible.But perhaps I'm missing something...

QuoteOriginally posted by: joetIs the line infinite in both directions? ie when a prisoner looks at the hats in front of him, can he see a finite or infinte number?The line has a definite start position, so there is a prisoner (say number 0) who can see all the hats other than his own.

I still say it can't be done: they have to guess their hat colour simultaneously, and thus cannot use any information from other prisoners' guesses when making their own. Are you sure you don't mean sequentially?As the question stands, for only a finite number of incorrect guesses, each prisoner must be able to guess his own hat colour correctly with probability one, give only the information he can gain from the other hats he can see. Perhaps I am going to be made to look silly, but I shall make the bold assertion that it's not possible as stated.

It's been over 10 years, so I feel enough time has passed to post the solution. It follows the Batman dying introduction bit of this video:

you changed the problem from N prisoners and M colors to an infinite number of prisoners and 2 colors, 0 and 1.