Three people enter a room. Each person is assigned a hat uniformly at random: either red or blue. Each person can see the hats of the two other people, but they can't see their own hats. Each person can either try to guess the color of their own hat or pass. All three do it simultaneously, so there is no way to base their guesses on the guesses of others.
If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose.
One more thing: before the contest, the three people have a meeting, during which they decide their strategy. What is the best strategy to maximize their odds of winning a prize?
At first glance, it seemed to me that there was no way to do better than 50%: only one of the three people tries to guess: red or blue. However, we can indeed do better. Here are 2 hints:
- Passing is always 'correct'. It won't make them lose unless everyone passes.
- If still stuck, try writing down the 8 possibilities for hat assignments.
Stop here if you'd like to try again with these hints.
Solution
Lets write down the 8 possibilities to assign the red/blue hats to 3 people
The key is to observe that there are always at least 2 people with the same color. In 6 of the 8 cases, there are 2 people with the same color, in the other 2 cases they all have the same color.
There is no strategy that accommodates all 8 cases. So we should optimize for the first 6 cases. Here, one person sees 2 hats with the same color, and has a hat of the other color. The other 2 people see hats of distinct colors. Hence they can agree on the following strategy
- If one of them see 2 hats of the same color, guess the opposite color.
- Otherwise, pass.
This strategy will only fail when they all have the same colored hats, working in 75% of the cases.
Sem comentários:
Enviar um comentário