1
$\begingroup$

This is a variant some of the existing questions on this exchange, but I can't see this exact problem.

Basic example duplicates this question

  • Some prisoners are going to be lined up, all facing forward.
  • A hat, either black or white, will be placed on their head.
  • The prisoners at the back of the line can see all of the hats in front of them, but they can't see their own, or behind them.
  • The prisoners at the front of the line can hear the people at the back of the line.
  • The prisoners can strategise before hand.
  • The prisoners have a perfect memory.
  • This is a logic puzzle, they don't use an vocal variance or intonation to communicate, they only say 'black' or 'white'.
  • Starting at the back of the line, the prisoner guesses the color of their hat, and if they are correct, they are free to go.

The strategy for this is fairly straight forward, and all of the prisoners except the last one are guaranteed to go free.

Basically, the prisoner at the end of the line counts the number of white hats, and if this number is odd he says 'white' and if it is even he says 'black'.

The person in front of him can now deduce, by counting the number of white hats in front of him if he has a white or black hat, and the person in front of him, by keeping track of what the previous people have said can similarly deduce what color hat they have.

Now with mulitple colors!

Now let's extend the problem, and deal with more than two colors of hat. If we are ok with three prisoners dying, how many different color hats can we strategise a solution for?

I don't know the answer, but as far as I have reasoned, it is at least 10.

Improve this question
$\endgroup$
3
  • $\begingroup$ Actually, I guess this has been asked here before, cmiiw. However, I do have a strategy with multiple colors and everyone but the last prisoner will survive. $\endgroup$
    – athin
    Jun 18, 2020 at 4:53
  • 1
    $\begingroup$ Does this answer your question? Hats and Aliens That question is only about hats of two colours, but the second answer there generalizes it to any number of colours. $\endgroup$
    – Jaap Scherphuis
    Jun 18, 2020 at 6:06
  • $\begingroup$ @Ja that is the right dupe $\endgroup$
    – dwjohnston
    Jun 18, 2020 at 7:14

1 Answer 1

Reset to default
4
$\begingroup$

I'm pretty sure you can easily extend the strategy to guarantee the survival of all but the first prisoner regardless of the number of colors.

Say there's $x$ colors. Each color will be assigned a number $0$ through $x-1$. The first prisoner counts the sum from the color numbers of hats they see (let's say $s_0$). Then they say the color associated with $s_1 \text{ mod } x = p_1$. The next prisoner counts all the hats they see (let's say $s_2$). Then they know they have the color $(p_1 - s_2) \text{ mod } x = p_2$ (the mod operator here returns a positive value when given a negative). The third prisoner (who sees $s_3$) can figure out their color as the one associated with $(p_1 - p_2 - s_3) \text{ mod } x = p_3$. This then continues for the rest of the prisoners with prisoner $n$ saying the color associated with $(p_1 - p_2 \ldots - p_{n-1} - s_n) \text{ mod } x = p_n$

Improve this answer
$\endgroup$

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