The Classic Blue-Eyed Monks Puzzle

[dreev]

This one is such a classic and so well-known that there’s a hilarious and delightful Slate Star Codex short story [archive link] about it, which I highly recommend, but only after you’ve puzzled over this puzzle…

Ok, here it is.

There is an island inhabited by monks with very rigid rules that they live by. Most strikingly, they believe that blue eyes are evil and if a monk finds out they have blue eyes they must commit suicide that very day.

Another rule is that, despite everyone seeing each other every day, they cannot communicate in any way whatsoever. That, combined with the fact that there are no reflective surfaces on the island, means that the blue-eyed monks never find out their eye color and so all is good for years and years.

But one day a visitor comes to the island and before they leave, remarks for all to hear that they’ve never seen such beautiful blue eyes as on this island.

That fateful comment sets off a chain reaction of reasoning by which the monks can logically deduce their eye color!

How do they do it and when do they figure it out?

Assumptions:

• every monk sees every other monk all the time but no information passes between them
• again, if a monk concludes they have blue eyes they kill themself the same day, so at dawn the next day, every other monk knows definitively that they didn’t kill themself
• ok, technically “I have / have not killed myself” is information but that’s it
• all monks are perfectly rational and obey the monk protocols impeccably
• (also everyone knows that and everyone knows that everyone knows that and everyone knows that everyone etc etc)
• the visitor’s announcement is made out loud publicly with everyone present
• (so the “everyone knows and everyone knows that everyone knows etc” thing applies to the announcement too)
• the visitor adds nothing but their observation that there exist blue eyes on the island

This is a pure logic puzzle. No tricks, just raw Slytherin reasoning.

I plan to post a solution soon because I want to get to the Fiendish Followup which everyone who thinks they understand blue-eyed monks perfectly well gets wrong!

PS: Let’s not bother with spoiler tags for this one.

PPS: See the fiendish followup!

[insti]

How many monks did the visitor interact with (enough to notice their eye color)?

[grayson]

If there is only one monk with blue eyes, he will kill himself at dawn, because he will see no blue eyes elsewhere and know the blue eyes must be his. All the other monks will then know they must have red eyes, or the dead monk wouldn’t have known his were blue.

If there are two monks with blue eyes, neither will kill himself the first day, because he might himself still have red eyes. None of the other monks will kill themselves, either. However, upon seeing the other blue-eyed monk still alive the next dawn, both these monks will know they must also have blue eyes (because all the other monks have red ones), and both will kill themselves. The remaining monks (all red-eyed) will now know they have red eyes.

If there are three monks with blue eyes, none of them will kill himself the first day. Upon seeing the other two blue-eyed monks alive the next dawn, each will still not know his own eye color. Upon seeing the other two blue-eyed monks alive the second dawn, however, each will know that he, too, must have blue eyes, and all three will kill themselves. The remaining monks will now know they have red eyes.

This pattern continues as the number of blue-eyed monks grows. If there are B monks with blue eyes, the blue-eyed monks will kill themselves on the Bth dawn after the visitor’s pronouncement, and the remaining monks will know they have red eyes.

[grayson]

Er, where I wrote “red” it should have been “non-blue,” apparently… but the argument is otherwise unchanged

[halfplane]

@grayson

If there are three monks with blue eyes, none of them will kill himself the first day. Upon seeing the other two blue-eyed monks alive the next dawn, each will still not know his own eye color. Upon seeing the other two blue-eyed monks alive the second dawn, however, each will know that he, too, must have blue eyes, and all three will kill themselves. The remaining monks will now know they have red eyes.

I got the one- and two-monk cases fairly easily, but I didn’t realise that the puzzle was asking me to extend it further in this way, and didn’t spot that it was possible for 3 blue monks until I read this!

[narthur]

Ok, without reading anyone else’s solutions, here’s mine:

Any given individual on the island has these pieces of information:

1. There are blue-eyed monks on the island.
2. All the eye colors of the other monks on the island.
3. The number of surviving monks each day.

One way to approach the question is to look at the simplest scenario and work our way backwards. With a single blue-eyed monk on the island, the monk can be certain that he is blue-eyed, since at least one blue-eyed monk is on the island and all other monks are not blue-eyed.

With at least one blue-eyed monk other than the individual, I make the assumption that any individual monk only need pay attention to the other blue-eyed monks on the island, and can safely ignore any brown-eyed monks. While I believe this assumption works, I’m not certain how to justify it.

Given one additional blue-eyed monk on the island, the individual in question need only wait one day to discover if he is blue-eyed or not. If on the first morning the individual discovers that the other blue-eyed monk is dead, he can be certain that he is not blue-eyed, since the other monk acted as if there were no other blue-eyed monks on the island. However, if the other blue-eyed monk is still alive the next morning, he can be certain that he is blue-eyed, since the other monk would be dead already if he weren’t. In this case, both the individual and the other blue-eyed monk will be dead the following morning since they both have confirmed that they are blue-eyed.

If an individual sees two other blue-eyed monks, he will need to wait two days to know if he is blue-eyed or not. If, on the second morning, both of the other blue-eyed monks are dead, he knows he is not blue-eyed, since the other blue-eyed monks are behaving as if each only sees one other blue-eyed monk. On the other hand, if they are both still alive, then he can be certain that he is blue-eyed, too, since the other blue-eyed monks would already be dead if he weren’t. In this case, all three will be dead the following morning, since they have all had time to confirm that they are blue-eyed.

At this point we can see the general strategy. Each monk can see n blue-eyed monks, and must determine whether there are n or n+1 blue-eyed monks on the island. For an individual to determine whether there are n or n+1 blue-eyed monks, he must wait long enough to determine if the other blue-eyed monks see n or n-1 blue-eyed monks on the island. If n, the individual is blue-eyed. If n-1, the individual is not.

In pseudocode, here is the algorithm that the individual must use to determine whether or not he is blue-eyed:

n = count(blue_eyed_monks)

if (days[n] == "mass_suicide"):
    is_self_blue_eyed = false
else:
    is_self_blue_eyed = true

[a11]

How many monks did the visitor interact with (enough to notice their eye color)?

I don’t believe it matters. All that matters is the visitor interacted with at least one blue-eyed monk and that all the monks hear the visitor’s final statement (and accept it as true–the monks know the visitor to be truthful).

[narthur]

I’m still confused about something. In the case that there are more than one or two blue-eyed monks on the island, what is the real significance of the visitor’s pronouncement? They all already know that there are blue-eyed monks on the island. They haven’t received any new information. So why would they start counting the days from the visitor’s pronouncement?

[zedmango]

With N evil monks, each reasons hypothetically about the case where they’re not evil, leaving N-1 monks. In order to do so, they have to think about what those N-1 monks would each think, and those monks would have to reason hypothetically about the case where they’re not evil, leaving N-2 monks… all the way down to 1 monk, where the 1 monk doesn’t (in the sub-sub … sub-sub-hypothetical) know that there are any evil monks - until the visitor makes his comment.

That’s why the visitor matters.

With 2 monks, they all know there are evil monks on the island, but each of them doesn’t know the other knows. In other words, they don’t know they all know there are evil monks on the island.

With 3 monks, they know they all know there are evil monks on the island, but they don’t know that they all know they all know it.

And so on, adding one “they all know” each time. The visitor gives them perfect meta-knowledge. Now they all know they all know, and they all know they all know they all know, and so on.

So they have received new information!

[zedmango]

Some follow-ups. What happens if:

1. The speaker lied, and there are no blue-eyed monks.
2. One of the monks is deaf and didn’t hear the statement, but nobody knows this.
3. One of the monks is deaf and didn’t hear the statement, and N monks know (but they each think they’re the only one who knows, and they don’t tell).
4. One of the monks is deaf and didn’t hear the statement, and N monks know this, and all know they know, and all know they know they know, etc, and none of them tell.
5. The statement is “There are at least N blue-eyed monks on this island” and it’s true.
6. The statement is “There are at least N blue-eyed monks on this island” and it’s false.
7. The statement is “There are an odd number of blue-eyed monks on this island” and it’s true.
8. The statement is “There are an odd number of blue-eyed monks on this island” and it’s false.
9. The statement is “There are at most N blue-eyed monks on this island” and it’s true.
10. The statement is “There are at most N blue-eyed monks on this island” and it’s false.
11. The statement is “There are exactly N blue-eyed monks on this island” and it’s true.
12. The statement is “There are exactly N blue-eyed monks on this island” and it’s false.
13. There are N groups of monks on the island, and no group knows about any of the others.

[dreev]

Nice work, everyone! I like @grayson’s assumption that non-blue-eyed monks are red-eyed. But I also agree that any monk without blue eyes is irrelevant to the whole puzzle. They never communicate anything, not even by dying, since we know that monks only die via impeccable logical deduction (c’est la vie). If you don’t have blue eyes you’ll never deduce that you do. So the non-blue-eyed monks might as well be furniture for all the impact they have.

So. There are exactly n blue-eyed monks on the island and no others. The visitor makes their announcement (“there exists at least 1 blue-eyed monk”) on day 1.

(And I made it confusing by referring to dawn but let’s say that if you deduce your eye color you commit suicide that same day. Dawn marks the new day – the point when you deduce that any living monk did not figure out their eye color the previous day. I might edit to original for posterity [DONE] so thanks to everyone above for helping clarify that!)

Here’s my solution!

Hardcore Math Nerd Version of Solution

Theorem: All n monks simultaneously commit suicide on day n.

Proof by induction on n.

Base case (n=1): The one blue-eyed monk learns from the visitor that blue eyes exist and, seeing no other blue-eyed monks, deduces instantly by process of elimination that they must have blue eyes. Thus they commit suicide on day 1.

Induction hypothesis: For an arbitrary blue-eyed monk population of k, they all deduce their eye color and kill themselves on day k. Now consider the case of k+1 blue-eyed monks. They each observe k monks so by the induction hypothesis they all know that (if the blue-eyed monk population is really k) those k monks will all die on day k. But then they don’t. Therefore there must not be only k monks, there must be an additional one, and by process of elimination it must be themself. All k+1 monks reason that way and so all deduce their eye color on day k+1. QED

Version of Solution that Actually Tries to Get You to Believe it

We can build up the solution by starting with the trivial case. Imagine there’s just 1 blue-eyed monk. That monk learns from the visitor that blue eyes exist and, seeing no other blue-eyed monks, deduces instantly by process of elimination that they must have blue eyes. Thus they commit suicide on day 1. Duh.

What about the case of 2 blue-eyed monks? Each monk is looking at the other one going “oh that poor schmuck”. If you see exactly one blue-eyed monk and the visitor says there exist blue eyes then you expect that monk to commit suicide immediately. And then they don’t. Crap. The only reason they wouldn’t commit suicide is that they see another blue-eyed monk. Which, by process of elimination, must be you. Doh.

Now consider n=3 and imagine yourself as one of the blue-eyed monks, hoping the other 2 you see are the only 2. Well, if they’re the only 2 then the previous paragraphs proves exactly what will happen. They’ll die on day 2. But then they don’t. Crap. There must be a 3rd and it must be you. Doh again.

For n=4 it’s the same story. Each monk sees 3 others and we just proved that if there are 3 then they’ll die on day 3. If they don’t then there must not’ve been 3. But they each see 3 so they all simultaneously conclude that the real number is 4 with the 4th being themselves. Womp womp.

What about something like n=100? Well, you can keep walking that reasoning forward as high as you like, so it’s technically true for any n whatsoever!

Discussion

Of course in real reality this is ludicrous. I mean, even aside from the part about blue eyes being evil and calling the conclusion to commit suicide “rational” and all that. You can construct a realistic version where everyone gets a red or blue card on their forehead and you win a million dollar prize for deducing your card’s color, etc. Maybe you need a disincentive to guess. Whatever, we can stick with the monk version and just pretend.

It’s obvious 1 monk will deduce their eye color instantly, it’s pretty solid for n=2, just barely plausible for n=3, and then for n=4 or higher it’s suddenly completely ludicrous. No matter what kind of supergenius everyone is there is just no way that you can genuinely have confidence on day 4 that you have blue eyes just because the 3 monks you see failed to figure out to all commit suicide the previous day. Knowing they’re supergeniuses isn’t enough. You have to know they know they’re all supergeniuses and know that they all know they know that and … I think one more level but I can’t keep that straight because I’m not a supergenius. Eliezer Yudkowsky calls this the Law of Ultrafinite Recursion.

Anyway, I was going to move on to the Fiendish Followup in a separate post, but @narthur and @zedmango have (impressively) spoiled it a bit here. Still, I think I’ll continue undeterred because there’s a lot of fun discussion to have about the Fiendish Followup.

Nonfiendish Followups

But first, let me take a crack at @zedmango’s followups:

1. Lying visitor, no blue eyes: Every monk immediately commits suicide. Harsh.
2. Deaf monk: Everything happens exactly the same except the deaf monk fails to commit suicide. Everyone else does.
3. Partially-known deaf monk: This one stretches credulity even more since I think we want to assume that each of the N monks is incorrectly certain that they’re the only one who knows of the deaf monk. But I believe it doesn’t matter. All the monks except the deaf one still commit suicide on schedule. Knowing about the deaf monk doesn’t help you as long as there are non-deaf clueless monks who’ll be committing suicide on schedule. Knowing they’ll do so tells you your eye color when they don’t.
4. N-common-knowledge of deafness: Again, knowing of at least one non-deaf clueless monk is enough to infer your eye color when they don’t commit suicide on schedule. So you (and they) all will commit suicide on schedule. But if the deafness is common knowledge among all the monks then they survive. Because 2 monks (with one deaf) both survive. So a 3rd monk has no expectation of the deaths of the other 2. Etc.
5. Statement is "\ge N blue-eyed monks": I think you can just subtract N-1 from the original answer.
6. Same statement but false: If the visitor says, for example, there are \ge 2 when there’s only one then the blue-eyed monk can see the visitor is lying and… warn everyone else? Otherwise they’ll all immediately commit suicide, wrongly thinking they’re the 2nd blue-eyed monk.

I guess the lying visitor cases feel less interesting to me. The fascination of the puzzle is what you can infer based on others’ inferences, etc. You can make anyone infer anything (even 1=2) with false premises.

7. Odd number: They all die immediately, since they see an even number!
8. n/a
9. At most N: Nothing happens. They all already know they might have blue eyes.
10. n/a
11. Exactly N: Instant death.
12. n/a
13. N isolated groups: The visitor blares the statement over a loudspeaker across the island and each group hears it and whether or not there are other groups out there hearing it is irrelevant. The dynamics in each group play out as if it were the only group.

[dbyler]

Well, this was a fun discussion. Thanks for posting!