Red Hat vs Blue Hat | Puzzles for Interview - Interview Preparation PDF Download

Introduction 

A team of three people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player’s hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other’s hat colors, each player decides on a response which are one of the following :
“I have a red hat”, or “I had a blue hat”, or “I pass”

The player’s responses are recorded, but the responses are not shared until every player has recorded her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response. In other words, the team loses if either everyone responds with “I pass” or someone responds with a color that is different from her hat color. What strategy should one use to maximize the team’s expected chance of winning?

For example, one possible strategy is to single out one of the three players. This player will respond “I have a red hat” and the others will respond “I pass”. The expected chance of winning with this strategy is 50%. Can you do better?

Answer

Strategy for 75% Chance of Winning

Solution

1. Analyzing the Outcomes
With three players and two hat colors, there are eight possible outcomes. Six of these outcomes have at least one hat of each color, while the other two have all red or all blue hats. In the six outcomes with both colors, there will be a majority color and a minority color.

2. Identifying Majority and Minority Colors
Players can determine whether they are wearing a majority or minority color by looking at the other hats. If a player sees both a red and blue hat, they must be wearing the majority color. If a player sees two hats of the same color, they must be wearing the minority color, which is the opposite of the color they see.

3. Proposed Strategy
The goal is to have the player wearing the minority color guess their hat color, while the other players pass. The strategy is as follows:

• If you see both a red and a blue hat, then "pass."
• If you see two red hats, then guess "blue."
• If you see two blue hats, then guess "red."

4. Winning Chances

Using this strategy, the team will win in all six cases with at least one hat of each color. They will only lose in the two cases of all-red or all-blue, in which all players guess incorrectly. This means the team has a 75% chance of winning, which is a significant improvement over the 50% chance offered by other strategies.