Beeminder Forum

Blue-Eyed Monks: The Fiendish Followup

Recall the classic blue-eyed monks puzzle and its solution.

Here is the long-awaited Fiendish Followup. You think you understand blue-eyed monks. Let me disabuse you of that notion!

Ok, it’s clear that the visitor was necessary to establish the base case – to kick off the whole reasoning process about what the monks know that other monks know other monks know, etc etc. However, the only information that the visitor states (“there exist blue eyes on this island”) is something that (assuming more than 1 blue-eyed monk) every single monk already knew. The question: What was actually different after the visitor’s announcement?

Whatever’s different, it has to boil down to information – things that monks know (including knowing what another monk knows or doesn’t know). So as one of, say, 100 monks on the island, 99 of whom you already know to have blue eyes, what do you know immediately after the visitor’s announcement that you didn’t know before?

To be clear, we need an actual fact about the actual world that a monk didn’t know before the visitor arrived and does know after.

Common attempts to answer the Fiendish Followup involve things like the monks knowing that there’s now a synchronization point. That’s not good enough! Imagine that the visitor had said “I have no information to impart but any suicides that may happen, start counting NOW”. Absolutely nothing will happen in that case. If you can articulate why not, you’ll be on the right track! Another hint is that if the visitor went around whispering their statement to every monk, it wouldn’t change anything. They have to say it out loud in public.

PS: @narthur and @zedmango spoiled this a bit in the original thread so don’t read their replies if you want to take a crack at this on your own! Which I highly recommend doing. It’s so mind-bendy and so easy to fool yourself into thinking you’ve grokked it when you haven’t, if you just read other people’s solutions.

PPS: Another bit of clarification / heading off of some confusion I’ve seen with this puzzle: Are we sure that the visitor’s statement has to actually impart new information in the sense of a new true fact? The answer is yes, because these are infinitely logical monks. They do not kill themselves because they are tricked into it through some elaborate recursive process that the visitor kicks off. A monk only concludes they have blue eyes because they do have blue eyes and they deduced it by airtight logic. And they make every possible deduction instantly. So they’re making a new deduction as soon as the visitor speaks which means new information which means at least one new true fact about the world.

2 Likes

This, as stated, is false. The most important part of the information provided by the visitor is not the existence of blue eyes on the island. Indeed, every monk already knew about the existence of blue eyes (if there are at least two blue-eyed monks).

Let’s define the following family of propositions:
P0) There exists a blue-eyed monk on the island.
P1) All the monks know that P0 is true.
P1) All the monks know that P1 is true.
P3) All the monks know that P2 is true.

Pn) All the monks know that P(n-1) is true.

If no monks have blue eyes, Pn is false for all n.

If one monk has blue eyes, P0 is true, Pn for n > 0 is false, and even though P0 is true, not all monks know it. (Specifically, the one blue-eyed monk is the one who doesn’t know if P0 is true or not.)

If two monks have blue eyes, P0 is true and all the monks know it, P1 is true but not all the monks know it, and Pn for n > 1 is false. (Specifically, the two blue eyed monks don’t know if P1 is true or not: as neither knows if there is only one blue-eyed monk or two, and given that P1 would be false if there was only 1 blue-eyed monk, neither can have confidence that P1 is true.)

Likewise: If k monks have blue eyes, then Pn is true for all n < k, and false for all n >= k. For all n < k - 1, all monks furthermore know that Pn is true. However, in the case of n = k - 1, Pn happens to be true, and not all monks know it. (And specifically, it’s the blue-eyed monks who are the ones who don’t know it.)

So: no matter how many blue eyed monks there are (so long as there are more than zero), we know of one member of this family of propositions that is a) true; and b) not known by all of the monks.

Here’s a new proposition:
Pω) For each finite n, Pn is true.

The statement the visitor made implies the truth of Pω! This isn’t too surprising—the statement the visitor made changes not just what monks know about blue-eyed monks, but also what monks know about what monks know about blue-eyed monks, and what monks know about what monks know about what monks know about blue-eyed monks, and so forth.

Let’s break it down into the following stages:
S0) As all the monks heard the visitor’s statement (which asserted the truth of P0), all the monks know that P0 is true.
S1) All the monks can reason that S0 happened to all the monks on the island, not just them—so they know that all the monks know P0, so they know that P1 is true.
S1) All the monks can reason that S1 happened to all the monks on the island, not just them—so they know that all the monks know P1, so they know that P2 is true.

Sn) All the monks can reason that S(n-1) happened to all the monks on the island, not just them—so they know that all the monks know P(n-1), so they know that Pn is true.

For any finite n, each monk can, by reasoning through the stages S0 to Sn, come to know that Pn is true.

Thus, each monk can come to the conclusion that Pω is true—that is, that Pn is true for each finite n.

So yes, the visitor’s statement was just P0. But the information the visitor provides by making that statement is much greater: it is at least Pω.

Confusing between these two things is exactly what’s at issue here—so it’s kind of unfair to start out by framing the question in that particular way.

But be that as it may—my above description of all this is also the full solution to the problem. Before the visitor’s statement, there was an n such that Pn was true, but not known by all the monks. As soon as the visitor made the statement, things changed drastically: for all finite n, Pn became both true and known by all the island’s monks. At least some of the monks learned something: specifically, the truth of Pn for a certain value of n.

3 Likes

Ah, thank you! Let me head off some of that confusion by editing my post to say “information the visitor states” instead of “information the visitor provides”!

[moved clarification to top-level post!]

(I think @zzq has nailed this one but I plan to post my own write-up of the solution which I’m hoping can be easier to digest for less mathy people. (I did do a similar thing with a list of numbered facts that monks might learn.) I think mostly you have to work this out for yourself before it will really make sense. Feel free to post your solution even if it’s ultimately entirely redundant with @zzq’s – I think mine will be!)

1 Like

Unless there is exactly one monk with blue eyes, of course!

2 Likes

Nice. Saying this without having tried to follow it beyond the n=2 case because I’m lazy and believe I’m already familiar with the concept:

Common knowledge, right? As in: x knows fact, x knows that y knows fact, x knows that y knows that x knows fact, etc.

Steven Pinker talks about this in the context of psychology – not sure if I read about it in one of his books or via his twitter account.

To be much more serious than was intended I’m sure (sorry): This seems quite a timely puzzle to me. In lockdown, with many people working from home, but with social media, I suspect we have more mutual knowledge than we know how to handle, and less common knowledge than would help us successfully communicate about difficult issues. I suspect that working from home cuts off opportunities for common knowledge to spread there.

For the maybe 0-sized set of people who love this sort of thing but haven’t come across Raymond Smullyan’s books, go and search for them! Mind you, though they’re presented in an informal and elementary way, and they’re fascinating, AND he uses it to explain deep and important ideas in logic (for example “To Mock a Mockingbird” leads up to Goedel’s famous theorem), unless you’re either seriously motivated or more able than me, you may find it’s like that old story about a boy whose father cures him of the desire to smoke by making him smoke a whole box of cigars (yes, in the story it’s always a boy and always the father).

2 Likes

Here is my attempt without having read the other solutions. First, the solution to the original puzzle and then to the follow-up.

Hypothesis: All blue-eyed monks kill themself on day T(b)=b, where b is the number of blue-eyed monks.

Trivial case:

T(1) = 1

If b=1 the blue-eyed monk can see that all other monks are non-blue-eyed and kills himself immediately.

T(b + 1) = T(b) + 1

If b monks are still alive after b days each monk must conclude that there are at least b + 1 blue-eyed monks which means he himself is blue-eyed for the case that he sees b blue-eyed monks. Hence, all b + 1 monks kill themselves on that day.

If we remove the statement that there are blue monks our base-case fails and the argument does not work. All monks live happily ever after.

1 Like

No monk knew about their eye color but without the synchronization point they also don’t have any way to figure out - as perfectly rational as they are - whether they have blue eyes. Knowing they have a way to now follow their ethical rules thanks to the visitor’s announcement, and knowing each other monk is perfectly rational, they all start the process. Why’s this incorrect, as you seem to say this is wrong unless I misunderstood?

It’s almost like the visitor implicitly made all the perfectly rational monks communicate without them having to communicate!

1 Like

(I unspoilered you cuz the forum doesn’t let me quote-reply otherwise. Also I don’t think your answer is spoilery – because it’s all wrong! :))

Actually it’s not that this is wrong, just that it’s not identifying a new fact that the monks learned when the visitor spoke!

Again, a synchronization point isn’t enough. Let me move my “another bit of clarification” into the top-level post, in case that helps… [done!]

Wait, are you purporting to have solved the fiendish followup here? I think your solution to the main puzzle is impeccable but I don’t think you’ve made progress on the followup yet! You’re quite correct that the visitor’s statement is necessary as the base case in the induction. But when there are 100 monks (or, say, 3 monks) what is the actual new fact that those N monks are learning?

Thanks for pushing me. It’s so weird because I understand what you are asking me to explain, and yet I am not sure if I can do it in a better way.

I mean, propositionally, it is clear that the argument cannot work if the one blue-eyed monk does not know his color. That’s just the basic logic.

Also, in a participatory sense (like if I were one of the monks), I know that if there are three monks and only one is blue-eyed, the other two monks know that the one monk cannot come to the correct logical conclusion. Therefore they cannot come to the right decision either because they rely on him for their reasoning and the chain continues.

So in a way, I know that the information “there are blue-eyed monks” from an external source is essential. Yet, I cannot entirely point my finger on what precisely the information is. Maybe something like “the knowledge that all other monks are now perfectly capable of doing their reasoning”?

PS: I read through the other answers and still feel the same.

1 Like

Ha, you are perfectly capturing why this is so fiendish! Your proposed “the knowledge that…” isn’t it. Or, I mean, it’s hinting in the right direction, but the actual fact “other monks capable of doing their reasoning” was always true and known. What reasoning they actually do has changed and the reason it’s changed is because they’ve learned a new fact. What fact is that??

Well, before I decide how many hours to spend feeling like I have a tiny brain, is the solution going to be a “a-ha, of course! that totally makes sense!” or a “hmmmm, yeah, I guess… maybe? not totally convinced” kind of solution? :stuck_out_tongue:

1 Like

Thanks for perfectly summarizing my feelings. I second this question.

2 Likes

Ha, astute question! I think it’s an “aha!” but it’s mindbendy enough that I don’t feel all that confident that you’ll agree. I plan to add my solution (which is a lot like @zzq’s but more prosaic, maybe) in a couple days…

1 Like

Here’s my solution!

Actually let me start by jumping straight to an answer, though not a complete one, using chains of I-know-you-know-they-know facts. I’m not sure whether to call this a warmup or throwing us into the deep end.

Consider all the possible numbers of monks:

  1. I.e., just you. You did not know there were blue eyes. Now you do.

  2. Just you (monk 2) and monk 1. You knew there were blue eyes but you didn’t know monk 1 knew. Now you know he does.

  3. You (monk 3) plus 1 and 2. You knew monk 2 knew but you didn’t know monk 2 knew that monk 1 knew. Now you know she does know that 1 knows.

  4. You knew that monk 3 knew that monk 2 knew but you didn’t know that monk 3 knew that monk 2 knew that monk 1 knew. Now you know he does know that 2 knows that 1 knows.

And in general, with you as monk n:

You didn’t know that monk n-1 knew that monk n-2 knew … that monk 2 knew that monk 1 knew. Now you know that n-1 does know that n-2 knows … that 1 knows.

Full Solution

As with the original puzzle, the case of 1 monk is trivial. The visitor’s statement is, in fact, the new fact. “There exist blue eyes.” Call that \text{Fact}1. The single blue-eyed monk thinks: “I did not know that. Now I do. Crap.” I.e., they learned \text{Fact}1 when the visitor spoke.

What about 2 blue-eyed monks? If I’m one of those monks, I’m thinking, “Yes, I knew there were blue eyes. Namely, that poor blue-eyed schmuck. What I didn’t know was that he knew that. But I just now heard the visitor tell him. So now I know that he knows.” That’s the new fact: “Other-monk knows there exist blue eyes.” Both monks learn that from the visitor. We’ll call that \text{Fact}2. Another way to state it is like so:

\text{Fact}1: There is at least one blue-eyed monk.
\text{Fact}2: Everyone knows \text{Fact}1.

Let me say it again in a way that will be easier to generalize. In the 2-monk case – call them A and B – both monks know \text{Fact}1 already, because they see each other. They do not know \text{Fact}2. In particular, A thinks B doesn’t know \text{Fact}1. \text{Fact}2 is that everyone (B in particular) knows \text{Fact}1. That’s the thing A doesn’t know because A thinks (hopes) B is in the dark. Until the visitor comes and blurts out \text{Fact}1 in front of B like an idiot.

Notice that \text{Fact}2 was already true, but neither monk knew it! Just like \text{Fact}1 in the 1-monk case.

Now add another possible fact which may or may not be known to a blue-eyed monk:

\text{Fact}1: There is at least one blue-eyed monk.
\text{Fact}2: Everyone knows \text{Fact}1.
\text{Fact}3: Everyone knows \text{Fact}2.

In the 3-monk case, it’s \text{Fact}2 that everyone already knows. Why? Because each monk, seeing 2 others, knows by the above reasoning that, in the 2-monk case, everyone knows \text{Fact}1. (This is still pre-visitor.) If each monk knows that everyone knows \text{Fact}1 then each monk knows \text{Fact}2. That’s what \text{Fact}2 means: "everyone knows \text{Fact}1".

So every monk knows \text{Fact}2, which is to say that \text{Fact}3 is true. Not every monk knows it, but it’s true.

Then the visitor speaks and what happens? Immediately they all know \text{Fact}3. In fact, the visitor’s statement makes them all immediately know every fact from \text{Fact}3 to \text{Fact}\infty [*] but \text{Fact}3 is enough for all 3 to deduce, after 3 days of no suicides, that they themselves have blue eyes. Hence their deaths on night 3.

In general, we have this list of possible facts:

\text{Fact}1: There is at least one blue-eyed monk.
\text{Fact}2: Everyone knows \text{Fact}1.
\text{Fact}3: Everyone knows \text{Fact}2.
\text{Fact}4: Everyone knows \text{Fact}3.
etc.

With n blue-eyed monks, they all know \text{Fact}1 through \text{Fact}(n-1). As soon as the visitor speaks, they all know \text{Fact}n (and in fact every higher fact as well).

Therefore \text{Fact}n was the already true fact that each blue-eyed monk learned from the visitor’s public statement. QED.

Denouement

I think this proof is solid but trying to translate one of those newly learned facts into a single English statement, even for the 3-monk case, breaks my brain every dang time:

With 3 monks, they all know there are blue eyes and they all know that everyone knows that (they see 2 others seeing each other) but – until the visitor – they don’t know that everyone knows that everyone knows.

(Maybe I can just barely grok that but with 4 monks it’s utterly hopeless.)

By expressing each fact in terms of the previous one we can prove it without holding the whole card house in our head. We establish that the visitor makes \text{Fact}2 known to both A and B in the 2-monk case. So with n=3, each blue-eyed monk, thinking it is the n=2 case, knows that’s what’s playing out and that \text{Fact}2 (something each monk already knew) is, post-visitor, now also known to the others. Well, "everyone knows \text{Fact}2" is exactly what \text{Fact}3 is. So the visitor has in fact made all 3 blue-eyed monks aware of \text{Fact}3.

Which sadly seals their doom within 3 days’ time! Being infinitely intelligent and perceptive is the worst.


Footnote

[*] That’s known as “common knowledge” – when everyone knows something and everyone knows that everyone knows it and everyone knows that everyone knows that everyone knows … ad infinitum. You get common knowledge by saying something out loud with everyone present. So that’s a critical assumption in the puzzle and it’s why, if the visitor went around whispering to every monk “there are blue eyes on this island”, they’d each say “duh” and nothing would change.

Relatedly, it’s not enough for all the monks to be perfectly rational. There has to be common knowledge of that as well. They all have to know they’re all perfectly rational and all know that they know that and all know that they know that they know that, etc etc. Any iota of doubt anywhere in that chain and the entire reasoning falls apart and they can survive careless visitors just fine.

I feel like I owe a reply to this thread. Thanks for the solution @dreev.

For me, this is a pretty obvious case of a

hmmmm, yeah, I guess… maybe? not totally convinced

kind of solution. Don’t get me wrong. This is a great summary, but I feel like I have kind of said the same think (or at least meant/thought). Haha.

Anyways, I enjoyed this. It’s a nice riddle. It would be cool to make a YouTube video about the monk-problem with cute animations of blue-eyed monks.

1 Like

A youtube video about this would be awesome, but nothing is going to top this delightful and hilarious short story based on this puzzle: https://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-blue-eyes-blue/

1 Like

You kind of did - you just didn’t spell it out in full detail. It’s the “fact N” that the monks are learning.

1 Like

That was a hilarious read. Thanks for sharing.

And I learned what a Mersenne Prime is.

Ahhh. Now it clicked for me. That was the

a-ha, of course! that totally makes sense!

answer I was looking for.

2 Likes