[Blofeld]

I will say that there's a fairly easy optimality proof for the best solution(s).

[mink]

Each prisoner can see only one of 2 different situations:

A: All other hats have the same color
B: One of the other hats has a different color than the other 2

If the distribution of colors is 3-1, they succeed if they guess the other color in A. They also succeed if the guess the majority color in B. Only one of these strategies is needed; they could well pass in the other case.

If the distribution of colors is 2-2, they succeed if they guess the minority color in B. If one sees A he knows it cannot be 2-2.

If the distribution is 4-0, the succeed if the guess the same color in A. If somebody sees B, he knows it cannot be 4-0.

The last 2 strategies can be combined, thereby winning in all 2-2 cases and in both 4-0 cases. But they can also agree on one of the 3-1 strategies. No matter on what they decide, they have always a 50% probability to get it right.

If the 3-1 strategy and the 2-2 strategy could be combined in some way, they might achieve a success rate of 87.5%, but I doubt that that is possible given they have to guess simultaneously.

Karl

[han]

Blofeld, on Nov 21 2007, 09:58 AM, said:

I'm intrigued, now, Han - what did you think the problem was? There's obviously a range of interesting problems here.

I understood the problem, just not the solution. I know the solution to the 4-person problem now but I haven't had a chance to really think about it. I haven't thaught about the n-person problem yet so please don't give away the solution to that Owen.

[han]

Well, perhaps Owen could post the solution. I have found a fairly easy way to show that you cannot do better than 3/4 with 4 people, but I'm ashamed to admit that I do not know the best solution when there are n people. All I know is that the probability of success goes to 1.

[zasanya]

I have come to the onclusion you cant do better than 75%.You have to treat each pproblem as if it was 3 people problem .Please tell me i am wrong.

[david_c]

Hannie, on Dec 1 2007, 03:50 AM, said:

Well, perhaps Owen could post the solution. I have found a fairly easy way to show that you cannot do better than 3/4 with 4 people, but I'm ashamed to admit that I do not know the best solution when there are n people. All I know is that the probability of success goes to 1.

I've seen this problem before, and I think I was told it hadn't been solved for general n. Though your observations are clearly true.

[jtfanclub]

OK....

I tell the guard in advance "I'm guessing whatever Max guesses", while Max isn't in the room.

Max comes out, and announces the color of my hat.

I have, simultaneously, guessed the same color.

I will always be right.

[david_c]

Also, if you like this problem, try doing the n=7 case. (I believe this is the smallest value of n for which you can do better than 3/4.) There's a relatively simple way to do better than 3/4 here, by

Spoiler

splitting up into a group of 4 and a group of 3 - the people in the smaller group will guess only when there are two hats of each colour in the larger group

. But it's possible to do even better than this.

[Blofeld]

(I don't have the time to post a properly explained solution now; someone else is welcome to, or I shall in a couple of days. Some comments, in hidden text:)

Spoiler

I don't know the general optimal solution.

The argument that you can't get better than 75% in the four-person case doesn't carry over to the 5-person case. After some fiddling with pen and paper I found that you can better it with 6 people; I ran a computer search to show that you can't do so for five people.

It's true (though slightly nontrivial) that you can attain the bound of only 1/2^n failure when you have (2^n)-1 people, and increasing the number of people can't make things worse, so the long term behaviour is within a factor of two of only failing one time in n.

Further generalisation of the problem: allow k hat colours instead of just 2. Now I can't even prove that the probability of success goes to 1 as n goes to infinity (for fixed k), though I think it's the case.

Challenge: What's the best you can do with three people, and three possible hat colours?

[david_c]

Blofeld, on Dec 2 2007, 02:30 AM, said:

Further generalisation of the problem: allow k hat colours instead of just 2. Now I can't even prove that the probability of success goes to 1 as n goes to infinity (for fixed k), though I think it's the case.

Let p ( win ) / p ( someone guesses wrong ) = R. Then

(i) R can be made arbitrarily large, as n goes to infinity. (Strategy: if you don't see anyone with a hat of a certain colour, then guess that colour. Otherwise don't guess. A bit boring to check that this works, but it "obviously" does.)

(ii) Given a strategy for n people with a certain value of R, there is an obvious strategy for s.n people which has the same ratio R, such that p ( no-one guesses ) goes to 0 as s goes to infinity.

Of course, the bound that you get is awful, but ...

Quote

Challenge: What's the best you can do with three people, and three possible hat colours?

Spoiler

Suppose the colours are black, red and green. Then three people who are red/green colour-blind will win 5/9 of the time by applying the two-colour strategy. You can't do better than 5/9.