Another puzzle ...

[david_c]

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

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:)

 

 

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]

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 ...

 

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

 

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.