A Curious Twist on the Cheating Husbands Brainteaser

Posted: May 30, 2010 | Author: | Filed under: Random Math | Leave a comment »

Here's a classic brainteaser:

Suppose I gather a group of fairly clever people and ask them to sit around a large table. I then place a hat on each person's head and explain,

"Each of you is now wearing a hat; some are red and some are blue. You are not allowed to look at your own hat, but you can see everyone else's. Every ten minutes, I'm going to bang this gong; at the sound of the gong, everyone who's sure she's wearing a red hat must leave the room. If you're sure you're wearing a blue hat, or can't yet determine the color of your hat, stay seated."

"Oh, and by the way, at least one of the hats is red."

If there are n people and m red hats (and n - m blue hats), what happens at each bang of the gong?1

The usual way to solve this problem is to use induction of m: that is, we first figure out what happens if there is exactly one red hat. We'll use this information to figure out what happens where there are two red hats, and then what happens when there are three red hats, and so on; the general argument for any number of hats will then become clear.

So what happens if there is one red hat? Let's say Alice is wearing it. Alice looks around the room and sees nothing but blue hats. She knows her hat is either red or blue. But it can't be blue, since if it were, there would be no red hats at the table, and I explicitly told her that I had passed out at least one red hat. So her hat must be red, and she gets up at the first gong.

What about the case when m is two? Say Alice and Bob are wearing the red hats. They can each see the other has a red hat, but are unsure of their own hat's color. In particular, Alice is thinking, "Bob is wearing a red hat, and my hat is either red or blue. If it's blue, then Bob is the only person wearing a red hat, and he will realize this immediately when he sees that everyone else, including me, is wearing a blue hat (by the argument in the previous paragraph). So if he gets up at the first gong, I'm wearing a blue hat. If he doesn't, it's because he also sees one red hat. In that case we must each be wearing a red hat, so we'll both get up at the second gong."2

So nobody gets up at the first gong, and both Alice and Bob leave at the second gong.

As we tackle the m = 3 case the general pattern should start becoming clear. Let's say Alice, Bob, and Cheryl have the red hats. Alice thinks, "I'm either wearing a blue hat or a red hat. If it's blue, then Bob and Cheryl will leave after the second gong. If they don't, I must be wearing a red hat, and I'll get up at the third gong."

This recursive argument hold for any m, and in general nobody will leave until the mth gong, at which point everyone with a red hat leaves simultaneously.

This well-known brainteaser is sometimes called the Cheating Husband Problem or Josephine's Problem, and is given as a cute "word problem" illustrating the principle of induction. But the problem becomes truly interesting when you impose the following small twist: suppose that, say, n = 17 and m = 5. Ordinarily, all five people wearing red hats will leave at the fifth gong. But instead of reciting the above instructions the participants, I forget to tell them the last part, about there being at least one red hat. What happens now? You may want to ponder on your own before reading on.

One thing to notice is that the information I've forgotten to tell the participants is nothing they don't already know: since there are five red hats, everyone can see either four red hats (if they're also wearing a red hat) or five red hats, and so can deduce that there is at least one. So surely it makes no different that I left this part out, right?

On the other hand, the inductive argument above breaks down: if Alice were the only one wearing a red hat, and I forgot to tell here there was at least one, she would have no way of deciding if she were wearing a red or blue hat, and would remain seated forever. Since this base case no longer works, the entire chain of reasoning telling us what happens when there are two, three, four, and five red hats is also broken: so if it's still true that all five people wearing red hats get up at the fifth gong, we're going to have to arrive at that conclusion using an entirely different argument.

So let's say Alice, Bob, Cheryl, Devin, and Eddie are wearing red hats, and try to trace through what the heck is going on. Alice might think,

"I am wearing either a blue hat or a red hat. As before, let's suppose my hat is blue and figure out the consequences. Bob will look around the room and see three red hats, and think,

""I am wearing either a blue hat or a red hat. If it's blue, then Cheryl will look around the room, see two red hats, and think,

"""I am wearing either a blue hat or a red hat. If it's blue, then Devin is seeing one red hat and will think,

""""I am wearing either a blue hat or a red hat. If it's blue, then Eddie is seeing all blue hats, and can't determine whether or not his hat is red, and will sit there forever.

If it's red, then both of us are seeing one red hat, and going through this exact same argument, wondering if the other is seeing a red hat or blue, and will sit like this forever.

Either way, I can't ever determine the color of my hat, so must sit forever.""""

If it's red, then Devin and Eddie are also seeing two red hats, and going through this exact same argument, and will sit like this forever.

Either way, Devin and Eddie will stay seated forever and I'll never determine the color of my hat, so I will sit here forever as well."""

If it's red, then Cheryl, Devin, and Eddie are also seeing three red hats, and going through this exact same argument, and will sit deadlocked forever.

Either way, ... ""

... "

So everyone stays seated forever.

What went wrong? Why did leaving out something everyone already knew change the outcome?

When I told all of the participants that there was at least one red hat, I implicitly gave them a lot more information than meets the eye: from my instruction, they can deduce that

I. There is at least one red hat.

A. Everyone knows that there is at least one red hat.

1. Everyone knows that everyone knows that there is at least one red hat.

i. Everyone knows that everyone knows that everyone knows that there is at least one red hat.

a. Everyone knows that everyone knows that everyone knows that everyone knows that there is at least one red hat.

...

In the second situation, where I forget the instruction, I is still true, since everyone can see either four or five red hats. A is also still true: those who see four red hats know that everyone can see at least red three hats. So are 1 and i, but a is no longer true: Alice can't be sure that Bob's sure that Cheryl's sure that Devin's sure that Eddie knows there is at least one red hat. Even though Alice herself is 100% positive that Eddie can see at least three hats -- the ones on the heads of Bob, Cheryl, and Devin!!

  1. For this discussion we're only interested in what happens until everyone with a red hat has left the room; afterwards, everyone is wearing a blue hat, and will be either undecided or sure of it, and so will remain seated, until the end of time. [↩]
  2. This argument relies on Bob being smart enough to figure out that he should leave at the first gong if he sees no red hats. We're assuming everyone is "fairly clever" to dodge this particular complication. [↩]