Three logicians play a game with colored hats. (That's always how the trouble begins.)
Each logician wears a hat, and that hat has a 50% chance of being red and a 50% chance of being blue. The probabilities for each hat are independent of each other. None of the logicians is allowed to see the color of her own hat. They may make a game plan before starting, but during the game they may only look at the other hats without communicating.
And yet, the logicians guess the colors of their own hats.
They guess simultaneously, writing their guesses on paper which are only revealed after all guesses have been made. They may write "red", "blue", or "abstain". If at least one logician guesses right and none guess wrong, then they win. Abstaining counts as neither right nor wrong.
What strategy should the logicians use to have the highest probability of victory?
This puzzle was taken from Haidong. He also asks what happens if there are 2k - 1 logicians. The general case is rather difficult, but you should at least try for 7 logicians.
Solution posted
Monday, March 7, 2011
Subscribe to:
Post Comments (Atom)
5 comments:
The three case is trivial. If you see 2 of the same color, guess the opposite color. Otherwise, abstain. In this way, there will always be at least one person who does not abstain (by the pigeonhole principle). There are exactly 2 cases where this plan will fail them: when they all three have the same color. Since there are 8 total cases, they will win 75% of the time. I'll get back to you on the general case ;P
For 7:
If you see three of one and three of another, abstain.
If you see four of one, and two of another, guess the minority color.
If you see five of one, and one of another, you're screwed anyway if your hat matches the minority, so guess with the majority.
If you see six all the same, guess the other color.
Loses on all-the-same (2 cases) and five-and-two (42 cases) and wins on the rest. There are 2^7=128 cases, for a win rate of 65.6%
I'm thinking this same program will generalize (starting with picking opposite when everyone else is the same and alternating minority/majority as you increase the size of the minority set until you reach half-and-half, at which point you abstain), but I have no idea what the win rate sequence might be off the top of my head.
The solution for 7 isn't optimal yet.
Hint for 7 logicians:
You can win 75% of the time by having three logicians play as before, and have the other four always abstain. But you can do better than 75%.
Having seen the id and xor solution for 7, it is pretty clear that it generalizes without changing it and results in a success probability of 2^n-1/2^n
Post a Comment