As is always the case with these things, the best solution is to keep your colored hats in a safe place where logicians can't find them. But let's play along with them for a moment.

**Strategy**

1. If the other two logicians have opposite-colored hats, then abstain.

2. If the other two logicians have the same-colored hat, guess the color not seen.

If all three hats are the same color, then all three logicians will guess incorrectly. If two hats are one color, and the last hat is the second color, then that logician will guess correctly while the others abstain. Thus, the logicians win 75% of the time.

**Proof of optimality**

Remember that each hat is colored independently. Therefore, whenever a logician takes a guess, they have a 50% of getting it correct and 50% of getting incorrect. Suppose that the logicians have a predetermined strategy. There are 8 possible ways their hats can be colored. Among these 8 possibilities, there must be an equal number of correct and incorrect guesses.

For example, consider the strategy above. Here are the 8 possible colorings (R=red, B=blue) and the number of correct/incorrect guesses for each:

RRR 3 incorrect

RRB 1 correct

RBR 1 correct

RBB 1 correct

BRR 1 correct

BRB 1 correct

BBR 1 correct

BBB 3 incorrect

Here there are a total of 6 correct guesses and 6 incorrect guesses. It's all a matter of distributing those guesses in an optimal way. The best way to do it is to spread out the correct guesses and group together the incorrect guesses. There can be at most 3 incorrect guesses for a single possibility. Therefore 75% is the best you can do.

**Adding more logicians**

(Warning: advanced puzzle-solving ahead!)

If there are N logicians, we can prove that the best strategy can win no more than N/(N-1) probability. Of course, there is no guarantee that there exists any such strategy, and it may be that the best strategy is worse than that.

It turns out, though, that for 2

^{k}-1 logicians, we can devise such a strategy. But describing this strategy is difficult. I think the best way to describe it is by listing the "losing possibilities". A losing possibility is a hat-coloring which will result in all the logicians guessing incorrectly. For example, in the strategy I described for 3 logicians, the losing possibilities were BBB and RRR.

When each logician looks at the other hats' colors, she tries to determine if the hats may be colored like any of the losing possibilities. If not, then she abstains. If there's a chance that it's a losing possibility, then she bets against it by guessing the other color.

For 7 logicians, I need to pick 16 losing possibilities in such a way as to correctly distribute the correct guesses. Rather than listing out all 16, I will list 4. The rest of the losing possibilities can be found by taking bitwise XOR operations of other losing possibilities. (0=Blue, 1=Red)

1110000

1001001

0101010

0011100

This solution is not unique. Rather than proving it, I will simply assert that this wins with 7/8 probability.

And here is a solution for 15 logicians, stated in the same format:

111000000000000

100100100000000

010101000000000

001110000000000

100000010000001

010000010000010

001000010000100

000100010001000

000010010010000

000001010100000

000000111000000

I leave it as an exercise to the interested and savvy reader to solve the general case for 2

^{k}- 1 logicians.

## 0 comments:

Post a Comment