6 prisoners, 36 hats, 6 colors. Is there a proper strategy?

Question

There are 6 prisoners and 36 hats of differents colors
(6 red hats, 6 orange, 6 yellow, 6 green, 6 blue, and 6 violet).

Each prisoner gets a hat, which can be any one of those six colors.
The colors of the hats are independent of each other and repetitions
are allowed. For instance, it may happen that all the hats are green.
Each prisoner can see only the colors of the five hats worn by the rest
five prisoners. No prisoner can see the color of his or her own hat.

The prisoners are to guess the colors of their own hats, writing down
their guesses on sheets of paper. No prisoner can see what other prisoners
are writing. No communication between the prisoners is allowed.

If at least one prisoner guesses correctly then all six prisoners go free.

The prisoners are allowed to plan out a strategy in advance,
and they hope to find a strategy which would guarantee them success
for every possible arrangement of hats. Is there such a strategy?
Either find one or show that it cannot exist.

Addition:
The prisoners can not see the left over hats.

The prisoners are to guess the colors of their own hats, writing down
their guesses on sheets of paper.

= (if you wish)

The players are to guess the colors of their own hats and they must all announce their guesses SIMULTANEOUSLY.




"The prisoners are allowed to plan out a strategy in advance."

"in advance" = before getting hats.

Thanks, Sentient! This is indeed the solution to the problem as it originally appeared in my posting (i.e. assuming that the prisoners can see who starts writing first).

Please, see, however, the additional details. Assume that the prisoners must all write their answers simultaneously or merely don't see each other when writing the answers.

Sorry for misleading.

Answer 1

I solved this problem, after considerable effort, when my friend posed it a couple months ago, as follows:

Use 0,1,...,5, for the six colors and do all arithmetic in mod 6. Let player k (0,1,...,5) choose the color: k - (Sum of all five visible colors) (Mod 6)

If h0,...,h5 are the actual colors of the six hats, let j=h0+h1+...+h5. Then player j will have guessed the correct color (hj) since:

j - [Sum of all five visible colors] = j - [j-hj] = hj

Answer 2

There is a similar (but simpler) problem: http://www.relisoft.com/science/hats.html



Three people enter the room, each with a hat on their head. There are two colors of hats: red and blue; they are assigned randomly. Each person can see the hats of the two other people, but they can't see their own hats. Each person can either try to guess the color of their own hat or pass. All three do it simultaneously, so there is no way to base their guesses on the guesses of others. If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose.

One more thing: before the contest, the three people have a meeting during which they decide their strategy. What is the best strategy?

http://www.relisoft.com/science/hats2.html

You are probably thinking that the best strategy can work only in 50% of the cases. The three people could designate one of them as the official guesser, who will say "My hat is red" while the two other pass. The guesser will be right half of the time.

Well, think again. There is a much better strategy. Consider the fact that if a person says "red" they will be right 50% of the time. The same with "blue." But when they say "pass," they are always right! Except, of course, when the two others pass as well. So you can see that there is a hint of a strategy that averages the three odds, 50%, 50%, and 100%, to something higher than 50%. You just have to cleverly avoid collisions between competing guesses.

The answer is here:
http://www.relisoft.com/science/hats3.html

In Yakart's problem, the condition
`If nobody guesses incorrectly' is absent (as well as the possibility to pass), so I can imagine that the prisoners can design a strategy with a higher probability of success as compared to the problem I refer to. However, I'm not sure that the perfect (100%) strategy exists.

Answer 3

I think I got it! I'm going to assume that the prisoners can see each other.

1. Number the prisoners 1 to 6. This is the order in which they will start writing their answers.
2. Give each prisoner a color, so P1 gets red, P2 gets orange and so on.
3. In the first minute, only P1 can write his answer, in the second minute, only P2 can write, third minute, only P3 can write and so on.
4. In the first minute, P1 will ONLY start writing if someone else is wearing a hat of the color assigned to him (in this case, red)
5. If P1 writes, the other prisoners will know that one of them is wearing red, and all will write red.
6. So we wait from the 1st to the 6th minute, and once someone writes something, then the rest will all record down the writer's assigned color.

Hope this is the solution! I had fun solving it! Cheers :)

UPDATE:
Yakart: I don't think there is a strategy to guarantee success.

Assuming everyone must write down the answers simultaneously, the best way to prove this is by simple probability. Each man has only a 1/6 chance of guessing his hat color correctly. This means that each man has a 5/6 chance of guessing his hat color wrongly. The chance of ONE of them guessing correctly is thus 1 - (5/6)^6 = 0.665


Anonymous: Your answer above involves a form of pausing as well, then going by your own logic, your answer (to the 'similar' question you proposed) too involves a form of communication and is just about as correct as mine.

Answer 4

If they can see the color of the other prisoners' hats, as well as the left over hats, it is entirely possible for them to figure it out. They just had to take note of all the hats, figure out which color is missing one, and that is the color they have on. For example, if all the prisoners are wearing a different color, one would only have to look at the remaining, see that 5 of each color are left over, and know that whatever color they do not see on the other prisoners is the color they have on. That is the only solution I can think of.

Answer 5

It may be possible for there to be such a strategy. I've seen it demonstrated for a simpler problem. Please give me a moment and I will find it for you.

The simpler problem is this:
Three men, members of a safari, are captured by cannibals in the jungle. The men are given one chance to escape with their lives. The men are lined up and bound to stakes such that one man can see the backs of the other two, the middle man can see the back of the front man, and the front man can't see anybody. The men are shown five hats, three of which are black and two of which are white. Then the men are blindfolded, and one of the five hats is placed on each man's head. The remaining two hats are hidden away. The blindfolds are removed. The men are told that if just one of the men can guess what hat he's wearing, they may all go free. Time passes. Finally, the front man, who can't see anyone, correctly guesses the color of his hat. What color was it, and how did he guess correctly?

The solution is this:
The back man can see the hats worn by the two men in front of him. So, if both of those hats were white, he would know that the hat he wore was black. But, since he doesn't answer, he must see at least one black hat ahead of him.

After it becomes apparent to the middle man that the back man can't figure out what he's wearing, he knows that there is at least one black hat worn by himself and the front man. Knowing this, if the middle man saw a white hat in front of him, he'd know that his own hat was black, and could answer the question correctly. But, since he doesn't answer, he must see a black hat on the front man.

After it becomes apparent to the front man that neither of the men behind him can answer the question, he realizes the middle man saw a black hat in front of him. So he says, correctly, "My hat is black."

I'm sure the solution to your problem uses the same principle, but I can't think of it at the moment. I will keep thinking about it, and if I think of the solution before you or another answerer, I will update my answer to reveal it to you.

Sentient: Writing/pausing seems to be form of secret communication. Another way to communicate would for a certain prisoner to hold a gaze with anyone with a hat of a certain color. It might work in real life, but it is not the right way for this type of logic problem. I think there's another way to do it, but I can't think of it at the moment.

Edit: OK, on second thought, I believe it is impossible for any of the prisoners to guess with 100% certainty the color of their own hat strategically in any case. I think it is because it is impossible for them to eliminate any possibilities regarding the color of their own hat. However, they may be able to make a guess based on the probability of their own hat being a certain color. It depends on how the hats are chosen. Is each color equally likely to be chosen, or are all the hats in some pool together? The probability of each color may vary in the pool method, but if the hats with different colors are kept separate and the color of the hat is chosen randomly (as opposed to the hat itself), then the probability of each color is constantly 1/6. If the hats are kept in a pool, their best option would be for each of them to guess one of the colors least represented among the other hats. If they are not kept in a pool, then the best strategy would be for them to all agree to choose a single color (actually, I don't think that creates an advantage or disadvantage over random selection . . . maybe someone could enlighten us in that respect?). I cannot think of any strategy that will guarantee their success for any arrangement for either of the selection schemes I have described.

Sentient: Yes, that was a spur of the moment thing. I didn't realize how dissimilar the questions were until I found the other question on my computer. The other one just reminded me of the question I had seen before. It's encouraging that someone else thinks the question is impossible to answer as well as I do.

Answer 6

The strategy does not require any math. Let us say the prisoner are numbered from 1 to 6. All they have to do is select a particular prisoner (in case that person is required to answer first then a second person as safety measure), and look at the Hat of the person to answer. Obviously the chosen one will know color of own hat.

I personally believe that you missed something in your question.

Answer 7

If I was a prisoner I'd pick the color with the highest probability of being worn by myself based on eliminating certain hats of the five other prisoners.