$12$ Prisoner Hat Problem with $5$ different Hats

Question

There are $12$ prisoners named $A,B,C,D,E,F,G,H,I,J,K$ and $L$ and each of them was given a hat with the number $0,1,2,3$ or $4$ on it. They cannot see what is on their own hat but can see what is on the other $11$ prisoners' hats.

The guard calls them forward in alphabetical order and asks them to whisper in his ear what number they think is on their hat. If they are correct they are allowed to leave otherwise they get executed.

Before the prisoners are given hats they are allowed to devise an optimum strategy so that the most prisoners leave with their life. Once hats are given no communication is allowed between the prisoners (including any sort of secret code).

What is the optimum strategy and how many prisoners can survive?

Answer 1

According to the OP's comments, later prisoners can observe the fate of earlier prisoners. But now it's easy to ensure that at least eight prisoners survive:

$A,B,C,$ and $D$ assume that the sum of all the hats modulo $5$ is equal to $0,1,2,$ and $3$ respectively, and base their answer on this assumption. As soon as one of them goes free, everybody else knows this sum, so they can answer correctly.

If none of them go free, the sum must be $4$. And of course if $A,B,$ or $C$ goes free, then $B,C,$ and/or $D$ are freed from their obligations, and will go free too. So the number of survivors can be anything from $8$ to $12$.

Answer 2

I will post this solution supposing you meant that their strategy is deterministic.

Answer is $2$. To see that this can be obtained, divide $10$ of them in two groups of $5$ and ignore the rest two prisoners. To see that $1$ prisoner can survive out of $5$ take this strategy: first prisoner assumes sum of all their numbers $ = 0$ modulo $5$, second assumes it is $1$ modulo $5$, ..., fifth assumes it is $4$ modulo $5$. So each prisoner whispers a number that would make total sum of their hats one of the five possible residues modulo $5$. It is now clear that exactly one of them will survive.

To see that in general it's not possible that $3$ will survive, consider all $5^{12}$ possible distributions of hats. Try to count total number of correct guesses by all prisoners in all of those distributions. Examine $5$ distributions that differ only in first hat. Since prisoners play deterministic strategies, first prisoner will guess correctly exactly once in those $5$ distributions. Now divide all of the $5^{12}$ initial distributions into groups of $5$ groups of $5^{11}$ distributions that differ only in number written of first hat. It follows that in all $5^{12}$ distributions, first prisoner is going to guess correctly exactly $5^{11}$ times. Same holds for all the prisoners. So, in total there will be exactly $12 \cdot 5^{11}$ correct guesses. It follows that average number of correct guesses is $\frac{12 \cdot 5^{11}}{5^{12}} = 2.4$, so there must be some distribution of hats so that $2$ or less prisoners guess their hat number correctly, regardless of their strategy.

Answer 3

The probability of a prisoner guessing his hat number is $\frac{1}{5}$

The probability of a prisoner not guessing his hat number is $\frac{4}{5}$.

In other words, the prisoner knowing other prisoner's hat number has no bearing on his guessing his hat number correctly. Each prisoner guesses independently of other prisoners.

P ( all guessed correctly) $={12\choose12} \frac{4^0}{5^{12}}$

P ( 11 guessed correctly) $={12\choose11} \frac{4^1}{5^{12}}$

...

P ( 0 guessed correctly) $={12\choose0} \frac{4^{12}}{5^{12}}$

This looks like binomial distribution and thus the expected number of prisoners who will survive $$\sum_{i=0}^{12} i{12\choose 12-i} \left(\frac{4}{5}\right)^{12-i} \left(\frac{1}{5}\right)^{i}$$

$$=\boxed{2.4}$$