9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ possible duplicate of Hats and Aliens $\endgroup$ – durron597 Mar 13 '15 at 17:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Engineer Toast Mar 13 '15 at 18:26
  • $\begingroup$ @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. $\endgroup$ – durron597 Mar 14 '15 at 13:50
7
$\begingroup$

Only one person must risk death when using the correct strategy.
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.

$\endgroup$
  • 1
    $\begingroup$ The math behind how other prisoners can always guess correctly: Also label prisoners 1-P. if the first prisoner (F) calculates the sum mod n of hats of the other prisoners (let's call it x), any other prisoner (G) can then calculate the sum mod n of hats of prisoners, skipping the hats of F and G (call it y). We know that y + (value of the hat of G) = x mod n, so we can calculate (value of the hat of G) = x - y mod n. More intuitively, the first guess encodes the hats of everyone but F, and each G can compare that to the encoding of the hats of everyone but F and G to find the value of G. $\endgroup$ – TheRubberDuck Sep 17 '14 at 18:06

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.