Beers, Muddy Children and Colored Hats: When Human Beings Are Perfectly Logical

Having fun with induction puzzles

For the readers unfamiliar with the joke: the idea here is that the first dude to answer wants beer, but doesn’t know if the others also want beer (and thus doesn’t know if everyone wants beer). The same is true for the second guy. The third one also wants beer. How does he know that everyone wants beer? Because if any of the other guys didn’t want beer, they would already know that not everyone wanted beer, and would have answered “No”. Note that they all know that the guy who asked wants beer, because if he didn’t, he would know that not everyone wants beer.

This joke assumes the four guys are all perfectly logical. In real life, of course, people aren’t always like that, and the guy who asks “Does everyone want beer?” would expect everyone to answer whether they specifically want beer. But despite this, we can discuss (and most importantly, solve) interesting problems were people are perfectly logical.

During a big party, 100 kids are playing outside when suddenly, one of the mothers gathers them around. She tells them that at least 1 of the children have mud on their face. In reality, as many as 87 of the children have mud on their face. None of the children know whether their own face is muddy; however, they are all great at logical reasoning.

Now that the children know that at least 1 of them has a muddy face, the mother says: “If any of you know for sure that you have mud on your face, step forward!” Unsurprisingly, none of the kids step forward. Then the mother says the same thing again: “If any of you know for sure that you have mud on your face, step forward!” Again, all kids remain where they are. This goes on for a while, until at the 87th round, suddenly all muddy kids simultaneously step forward. How did they figure it out?

Let’s start with a simpler version. There are 3 kids: Alice, Bob, and Charlie. Alice has mud on her face (but can’t see it). The mother says at least one of the three kids has mud on their face. Can Alice figure out she is the muddy one?

Yes. In fact, she can do so immediately: she sees Bob and Charlie have clean faces. If there is at least one muddy kid, it must be her!

Now imagine the same problem, but both Alice and Bob have mud on their faces. After the mother says at least one of the three kids has mud on their face, can Alice know she is one of them?

No. She sees Bob has mud on his face. So even if she has no mud on her face, the proposition “At least one kid has mud on their face” is true. She could have mud on her face — two kids satisfies the proposition “at least one kid” — but she can’t know for certain.

The situation is, of course, the same for Bob. So neither Alice nor Bob steps forward.

Then the mother asks again: “If any of you know for sure that you have mud on your face, step forward!” Now the situation is different. Alice knows Bob didn’t step forward earlier. This tells her something! If neither her nor Charlie had a muddy face, then Bob would have stepped forward: his situation would have been the same as Alice’s in the previous problem (with 1 muddy kid). So this tells Alice that at least one more kid besides Bob must have a muddy face. Since she can see it isn’t Charlie, it must be her. So she now steps forward!

Again, the situation is the same for Bob, so he also steps forward in Round 2 (that is, the second time the mother asks).

What if Alice, Bob and Charlie all have mud on their faces? Again, let’s take Alice’s perspective. In Round 1, nobody steps forward. This tells Alice nothing she doesn’t know: she already knew both Bob and Charlie saw another kid with mud on his face (Bob sees Charlie and vice versa). So she won’t step forward in Round 2 either. But neither do Bob and Charlie (they have the same perspective as Alice), and this does tell her something: it tells her that Bob and Charlie also see two muddy kids. After all, had they only seen 1, they would have stepped forward at Round 2! So Alice now knows that she must be muddy as well. She steps forward at Round 3, and, by symmetry, so do Bob and Charlie.

You might notice a general trend here: with n muddy kids, all muddy kids step forward at Round n. We can even prove this using mathematical induction! Well, to be honest, we’re proving that all muddy kids will step forward no later than Round n, but that’s good enough.

Base case. n = 1: we have 1 muddy kid. This 1 muddy kid sees there are no other muddy kids, so since there is at least 1 muddy kid, it must be her. She steps forward immediately: at Round 1.

Induction step. Assume that if there are n muddy kids, they all step forward no later than Round n. Now we must show that if there are n + 1 muddy kids, they all step forward no later than Round n + 1.

So let’s say there are n + 1 muddy kids. It’s Round n + 1. They see n muddy kids. But then they know they must be muddy themselves: otherwise, those n muddy kids would have stepped forward already, by our assumption! Our induction step is complete, and with that, our entire proof. Q.E.D!

Cool. So now imagine the following scenario.

You’re a guest at a gathering of 12 perfectly logical people — let’s call them the Logicians. At the start, Logician Supreme gives all 12 Logicians (including herself) a colored hat to wear. Note that nobody — not even Logician Supreme — knows the color of their own hat. All 12 Logicians stand in a circle, and Logician Supreme says:

I’m going to ring this bell here repeatedly. After each ringing, if you know the color of the hat, please leave the circle! I promise everyone can eventually know the color of their own hat, and I do expect everyone to leave at the exact right moment: that is, as soon as you can logically know what color your hat is.

The game proceeds as follows (as seen from above):

How did the logicians figure out when to leave the circle?

First of all, note that everyone knows their hat is the same color as the hat of at least 1 other Logician. After all, if that wasn’t the case, their hat could be any color and they could never guess it, which contradicts what Logician Supreme said. They also know this fact is true for every Logician there: nobody is wearing a uniquely colored hat.

But using this logic, both green hat wearing Logicians know they can leave when the bell first rings. Their reasoning is analogous to the reasoning of the muddy children: they see only 1 green hat, so they themselves must be wearing the other green hat. (Otherwise, the green Logician they see would be wearing a uniquely colored hat.) The same is true for the purple Logician, who both leave at the first ringing too.

The 3 red Logicians all observe that none of the other red Logicians leave at the first ringing. They therefore conclude they themselves must be wearing a red hat, because otherwise, the red Logicians they see would have left with the green and purple Logicians. So the red Logicians all leave at the second ringing.

At this point, you might be wondering why the five blue Logicians all leave at the third ringing. Wouldn’t they need 4 rounds?

No! Each blue Logician sees only blue Logicians at this point. They must be blue themselves, otherwise they are uniquely colored! Each colored subgroup in this problem is like the problem of the muddy children, with the extra realization that one’s color can’t be unique. That extra information makes that, within a subgroup of n Logicians wearing the same color hat, everyone leaves at Ringing n - 1: in terms of the muddy children problem above, it would be like the mother telling them at least two children have mud on their face.

As always, thanks for reading!