Saturday, April 2, 2011

Solution to logicians with hats

See the original problem

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 2k-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 2k - 1 logicians.

0 comments: