0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can prisoners see what happens to the prisoners before them? $\endgroup$ – Arthur Dec 18 '16 at 9:16
  • $\begingroup$ I guess there is no information about the the number of 0s, 1s, 2s, 3s and 4s ? $\endgroup$ – Fabrice NEYRET Dec 18 '16 at 9:55
  • $\begingroup$ I strongly doubt that there is a strategy which will save most prisoners, that is, more than $6$. Perhaps you mean "the most" prisoners, as many as possible. $\endgroup$ – Joffan Dec 18 '16 at 10:21
  • 1
    $\begingroup$ Prisoners can see if the person before leaves or is executed. $\endgroup$ – Ben Franks Dec 18 '16 at 18:23
  • $\begingroup$ @Arthur: How would it help me to see what happens to the prisoners before me? $\endgroup$ – TonyK Dec 18 '16 at 23:52
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Damn I was always splitting them into groups. Congratulations this seems like a very good solution. $\endgroup$ – Ben Franks Dec 19 '16 at 19:50
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What colours are you talking about? $\endgroup$ – A.Γ. Dec 18 '16 at 12:00
  • $\begingroup$ sorry, occasionally problems of this type are given in a way "prisoners are given hats of $N$ different colours" instead of "hats numbered $0$ to $N-1$", so I automatically wrote colour. I will edit my post. $\endgroup$ – prosinac Dec 18 '16 at 13:44
  • $\begingroup$ A specific strategy to show two can survive is for each prisoner in a group of $5$ to assume that the sum of their numbers $\bmod 5$ is a different value and guess the number for their had that makes the sum that value. You will save exactly one from each group of $5$. $\endgroup$ – Ross Millikan Dec 18 '16 at 13:50
  • $\begingroup$ I got told the answer was 3 or greater, I haven't actually figured out a strategy myself that can give 3 survivors guaranteed though. $\endgroup$ – Ben Franks Dec 18 '16 at 18:29
-1
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ You've computed the expected number who don't survive. (I.e., your index $i$ corresponds to the number that guess incorrectly.) $\endgroup$ – Barry Cipra Dec 18 '16 at 16:24
  • 1
    $\begingroup$ Your strategy doesn't guarantee that anyone would survive. Everyone could guess wrong. You are looking for a strategy that guarantees the most survivors. $\endgroup$ – Ben Franks Dec 18 '16 at 18:28
  • $\begingroup$ @BarryCipra, I have corrected it. Thanks $\endgroup$ – Satish Ramanathan Dec 18 '16 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.