11
$\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?

Improve this question
$\endgroup$
4
  • $\begingroup$ possible duplicate of Hats and Aliens $\endgroup$
    – durron597
    Commented Mar 13, 2015 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
    Commented Mar 13, 2015 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
    Commented Mar 14, 2015 at 13:50
  • $\begingroup$ "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. $\endgroup$
    – Hemant Agarwal
    Commented Dec 8, 2020 at 23:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Sep 17, 2014 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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