Mathclub Hat Problem

One of the students in Math Club recently put his own twist on the age old hat question: Assume you have n people, each of whom has a red or green hat put on them. They each don’t know what color hat they have on. However they can look around and see everyone else’s hat.

After getting to spend some time in a room looking at everyone else and their hats (they may not communicate in any way), they are each placed in separate cells and asked to say whether they have a red hat on, a green hat on, or “pass.” Everyone wins the game if at least one person says their right hat color, and no person messes up their hat color. Everyone loses the game if everyone passes, or if anyone says the wrong hat color.

The question is: what is the strategy that those wearing the hats should come up with beforehand? And can you come up with a formula giving the probability that n people win with that strategy?

To make the problem clear, let’s examine the three person case. The possible combinations of hats are:

RRR | RRG | RGR | GRR | GGR | GRG | RGG | GGG

The best strategy we could come up with is to say: if you see two opposite colors (a red and a green), say “pass”. If you see two hat of the same color, say you’re wearing the opposite color.

So you’ll lose with RRR and GGG (everyone sees two of the same color, so everyone will say the opposite color).

But you’ll end up winning with RRG, RGR, GRR, GGR, GRG, and RGG. Let’s look at RRG to explainThe person wearing the first red hat sees a red and green hat. So that person says “pass.” The person wearing the second red hat sees a red and a green hat. So that person says “pass.” The third person wearing the green hat sees a red and a red hat, so that person says “green” and is right! So RRG is a winning combination. Similar arguments follow for the other five.

Since there are 8 possible combinations of hats, and 6 of them have a winning strategy, there are 6/8 chances that everyone will come out a winner! (That’s a whopping 75%!)

So we’ve been investigating what the strategy will be for n people wearing red and green hats. So far, we’ve done pretty well. In fact, we’ve even gotten Pascal’s Triangle involved, which is always great.

And there seems to be a consensus among the students (though no proof yet) that if you have any even number of people playing the game, say 8, you can actually get better odds of winning if you ask another person to join in (so you’d have, say, 9 people playing). That seems totally counter-intuitive, that adding an extra person to play the game with you would lead to a better chance of winning. So if they’re right, I’ll chalk this problem up to a win.

PS. We did talk about the Bloxorz problem for two weeks, but students grew bored and tired of it. I still think it’s a great problem. Maybe one year a student will want to do an independent study on it, and ask me to be the adviser to the project.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s