Island of Blue-Eyed People

Expert Logician

For a little Friday Fun I have a logic puzzle for you. I’ll give you the puzzle at the beginning of the post, detour to some unrelated topics (to act as a spoiler barrier), and then explain the puzzle in the latter part of the post. I would encourage you to stop reading and think about the puzzle first — it’s quite a challenge. (I couldn’t solve it.)

The puzzle involves an island with a population of 100 blue-eyed people, 100 brown-eyed people, and a very strange social practice. The logic involved is downright nefarious, and even after reading the explanation, I had to think about it for a bit to really see it. (I still think it’s twisted.)

To be honest, I’m kinda writing this to make sure I understand it!

Randall Munroe (who writes xkcd and some cool books) calls this “The Hardest Logic Puzzle in the World.” That might be a little hyperbolic, but you couldn’t prove it by me. I can’t remember when I first encountered it, but I do remember I walked away shaking my head.

Recently, I started following Terry Tao’s blog, and his “Selected Articles” list includes a post about this puzzle. I read it, and this time I stuck with it. I didn’t solve it, but I did sort of kind of maybe in a way get a faint hint of a small glimmer. Maybe.

After reading the solution, I think I get it. To test myself, I’ll try to explain it later in the post. (Spoilers!) For now, here’s the puzzle (which combines Monroe’s and Tao’s formulations; I don’t like Monroe’s Guru or Tao’s ritual suicide):

As already mentioned, there is an island with 200 perfectly logical people on it, 100 of whom have brown eyes, and 100 of whom have blue eyes. They all belong to a sect that forbids any discussion of eye color. In particular, self-knowledge of one’s own eye color requires self-exile the following dawn. As such, all reflective surfaces are banned. No one may know their own eye-color, although of course they know everyone else’s.

One day a visitor comes to the island. Everyone attends a ceremony presenting the visitor with honors. Asked to speak, the visitor commits the faux pas of saying, “It’s rare to see a blue-eyed person in this part of the world.” Note the visitor does not single anyone out and is not looking at anyone in particular. There is no clue who the visitor means.

The puzzle is this: What, if anything, happens next? Specifically, do any islanders self-exile? Does the visitor’s statement change anything?

One theory is that the islanders don’t learn anything they don’t already know (there is a blue-eyed person on the island), so nothing changes.

Another theory is that the visitor has provided a new piece of information, and something does change.

I’ll give you a hint: the first theory is wrong.

§

The islanders are perfectly logical and will always make any logical deduction possible. They also always adhere completely to the requirements of their sect. Anyone who deduces their own eye color — and if logic permits, they will — self-exiles the following dawn.

The puzzle is purely logical and does not depend on any trickery or word-play. There are no secrets; every islander can see all the others. Assume the visitor immediately flees in shame without further comment.

Stop now and give it some thought. I’ll explain below.

§ §

I read (in The Guardian) about a poll (done by Radio Times) to determine the best James Bond actor.

Guess who won? (You get just one guess.)

They did it tournament style, pairing the actors in a face off.

In round one, Connery (56%) knocked out Daniel Craig (43%). Which is close, but I think Craig is establishing himself as the other really good Bond.

Round two pitted George Lazenby against Pierce Brosnan, which is maybe a bit weird. Lazenby only did the one film (it was his first film, too), whereas Brosnan did four (and was very well known by 1995).

I might have pitted Lazenby against Timothy Dalton, who wasn’t as well known and who only did two Bond films. That said, as much as I love On Her Majesty’s Secret Service (it has Diana Rigg in it!), I think Lazenby loses to either Brosnan or Dalton.

[There is also that the location used — that restaurant on the mountain top with only cable car access — it’s a real place in Switzerland, and I’ve been there. (Back in high school. Long story. But it made that film one of my favorite Bond films.)]

Round three apparently surprised people. Roger Moore (41%) lost out to Timothy Dalton (49%). Doesn’t surprise me at all. Moore is, for my money, the worst Bond (don’t get me wrong; I loved Moore as The Saint).

In the final playoff, Guesswho won (44%), with “surprise” runner up Dalton (32%) placing, and Brosnan (23%) just showing. Again, no surprise to me. Dalton was a “truer” Bond — so, for that matter, is Craig.

(Bond has an inner element of cruelty, which is why friendly quipping Roger Moore was such a bad Bond (and Brosnan to a lesser extent). It’s why Connery, Dalton, and Craig, are so good.)

§ §

NASA has a satellite image that compares pre- and post-blast damage in Beirut:

The Galveston Bay, Texas, explosion was a similar deal. Ammonium nitrate — great as fertilizer, but also a nitrogen compound.

The power of nitrogen bonds is… impressive. Various nitrogen compounds have been used in rocket fuels. (One of the more interesting books nonfiction I’ve ever read is Ignition!: An Informal History of Liquid Rocket Propellants by John Drury Clark, who was not just a rocket scientist, but a rocket fuel scientist.)

Some nitrogen compounds are so unstable it’s said they’ll explode if you just look at them. Or even if you don’t.

§ §

Back to the island (of blue-eyed people)…

Let’s review the situation: 100 brown-eyed people know there are 100 blue-eyed people and (as far as they know) 99 brown-eyed people.

Similarly, the 100 blue-eyed people know there are 100 brown-eyed people and (as far as they can count) 99 blue-eyed people.

It would seem the visitor saying there is a blue-eyed person adds nothing — everyone knows there is a blue-eyed person. (Half the island thinks there are 99, half the island thinks there are 100.)

But consider the situation with 100 brown-eyed people and only one blue-eyed person. While 100 people know there is a blue-eyed person, the blue-eyed person does not. The visitor’s statement in this case obviously adds new information for that one blue-eyed person.

For simplicity, let’s call the number of blue-eyed people N. In the case where N=1, the visitor obviously adds new information. The blue-eyed person reasons that, “Since everyone I can see has brown eyes, I must have blue eyes.”

Therefore, the next morning, that person exiles.

§

That seems pretty clear. Now consider the case where N=2, and there are two blue-eyed people on the island.

They both know there is one blue-eyed person. (The brown-eyed people all know there are two.) Each reasons: “If that person sees only brown eyes, they now know they have blue eyes and must exile.” Each expects the other to exile.

When that doesn’t happen, seeing brown eyes everywhere else, both realize they have blue eyes. Both exile the second morning.

(The brown-eyed folks know there are two, and expect both to exile the second morning.)

§

The logic continues with N=3. Each blue-eyed person sees two others and expects them to leave on the second morning per the logic for N=2.

When that doesn’t happen, each of the three realize they have blue eyes, and all three exile the third morning.

As before, the brown-eyed people see one more blue-eyed person than the blue-eyed people do, so the brown-eyed people expect the blue-eyed people to leave on the Nth day.

When N people do leave on the Nth day, it confirms there were N blue-eyed people and everyone left must have brown eyes. (Which, of course, means they all have to leave the next morning. The visitor cleared the island.)

§

The logic works for any N , because brown-eyed people always see one more blue-eyed person than blue-eyed people do.

The visitor clearly adds new information in the case of N=1, and the necessary logic based on that propagates upward as N increases.

Randall Munroe has a solution page if you want to explore this further. There’s also a good discussion in the comments of Terry Tao’s post about it. Lastly, the Wikipedia article about common knowledge (logic) discusses it.

§

Hope you enjoyed the puzzle. A nice little distraction for a Friday.

Stay safe, my friends! Wear your masks — COVID-19 is airborne!

About Wyrd Smythe

The canonical fool on the hill watching the sunset and the rotation of the planet and thinking what he imagines are large thoughts. View all posts by Wyrd Smythe

20 responses to “Island of Blue-Eyed People

  • Wyrd Smythe

    One thing I haven’t seen mentioned (although I haven’t read all the comments on Tao’s site) is that, after all the blue-eyed people leave, the remaining brown-eyed people all know they have brown eyes.

    Which means they have to leave the following morning.

  • Wyrd Smythe

    If I were to rank the Bond actors: Connery, Craig, Dalton, Brosnan, Lazenby, Moore.

    In truth, Craig and Dalton are kinda tied for second, and Brosnan and Lazenby are tied for third. Moore still comes in sixth, though. 🙂

  • J Ryan

    Hiya, that was fun. Glad you explained it.

    Do you write Corvid19 on purpose? I’ve noticed it a few times. I thought maybe it’s a Sci-fi inside joke?

    • Wyrd Smythe

      Damn! That’s a definite no! I’ve written about crows enough (corvids) that I constantly misspell the virus. I just had to go correct about ten posts. (I feel like I’ve been walking around with my zipper down. Thanks for saying something!)

  • SelfAwarePatterns

    The solution makes sense, but if everyone knew the number of each on the island prior to the visit, why did they need the visitor to figure it out? Seems like the island would have been cleared as soon as the counts were known.

    But then the question is, how were the counts known?

    • Wyrd Smythe

      But everyone doesn’t know the number of each prior to the visit. Brown-eyed people think the count is 100-blue, 99-brown, one (myself) unknown. That unknown could resolve as 101/99 or 100/100. Blue-eyed people have a mirror view: 100-brown, 99-blue, one unknown.

      So, logically, the common knowledge is that there are (at least) 99 blue-eyed people and 99 brown-eyed people, plus there is one unknown. That single unknown effectively masks the common knowledge of either group having 100 members. If that were known, all eye color would be resolvable.

      And that’s effectively what the visitor does — provide that last piece of information.

      In the case where N=1, that one person doesn’t know they have blue eyes. The visitor’s statement obviously adds a critical piece of information in that case.

      As the Wikipedia article on common knowledge explains, for N>1 there is a chain of knowledge.

      For N=2, each blue-eyed person knows there is a blue-eyed person, but doesn’t know there is a blue-eyed person who knows there is a blue-eyed person. (Only the brown-eyed people have that knowledge. They don’t know if there is a third person.)

      For N=3, each blue-eyed person knows there is a second blue-eyed person who knows there is a blue-eyed person. (Blue-eyed Carol knows that blue-eyed Bob knows that Alice has blue eyes, but doesn’t know that brown-eyed Dave knows Carol knows Bob knows about Alice.)

      Going back to the N=1 case, blue-eyed Alice doesn’t know anyone has blue eyes, but more importantly doesn’t know anyone else does. That’s the new piece the visitor adds — now Alice knows someone sees someone with blue eyes.

      As I said in the post: the logic is downright twisted!

      • SelfAwarePatterns

        Hmmm, okay, that makes sense. It’s a situation primed for a cascade. Although if I’m understanding correctly, it takes 100 days for everyone to figure out which side they’re on, whereupon they all have to exile. At least they’d be in exile together.

      • Wyrd Smythe

        It takes 100 days for the blue-eyed people to realize the 100th person is blue-eyed. The brown-eyed people all know there are (at least) 100 blue-eyed people, so they expect everyone to leave on the 100th day. (The blue-eyed people all expected the other 99 to leave on day 99.)

        But when the 100 blue-eyed people leave on day 100 and fulfill the brown-eyed peoples’ expectation, then they all realize they must all have brown eyes, so they leave on day 101.

        So on day 102 they’d all be together (assuming exile is a day away). That’s why I don’t like Tao’s version — in his, people who determine their own eye color commit ritual suicide in the public square at dawn. 😮

      • SelfAwarePatterns

        Ok, I’m going to try to forget this puzzle. Every time I stop thinking about it then return to it, I think it’s wrong. Then lots of thought makes realize it’s not wrong. Whereupon I stop thinking about it, think it’s wrong, and cycle again. 😛

      • Wyrd Smythe

        Ha! The intellectual equivalent of a musical earworm.

        It does seem like the visitor can’t possibly be telling them something they don’t know, so it can be hard to convince one’s intuition.

        It does depend on the assumption the visitor makes the same statement for any N, that the statement applies to any N. (It’s also a little artificial the visitor says there is a blue-eyed person when, in fact, there are 100, but that’s the framing of the puzzle.)

        FWIW, it apparently has been proven rigorously mathematically. Whether it would work as advertised in the real world is a whole other pot of pisceans.

      • SelfAwarePatterns

        Yeah, in the real world the islanders aren’t acting like actual human beings, where there’d be laziness, denial, and subterfuge.

      • Wyrd Smythe

        It could have been an island of Vulcans, except Rick Berman made them into humans, so there would probably still be laziness, denial, and subterfuge.

  • rung2diotimasladder

    Hey, hey! Fun puzzle!

    “But consider the situation with 100 brown-eyed people and only one blue-eyed person. While 100 people know there is a blue-eyed person, the blue-eyed person does not. The visitor’s statement in this case obviously adds new information for that one blue-eyed person.”

    This case seems a little different from the original. In this situation with only one blue-eyed person, how can that person know whether the visitor is telling the truth? Maybe the visitor isn’t being intentionally deceptive, but is color blind or sees brown eyed people as blue eyed, or something like that. For the blue-eyed person who has no reason to think anyone on the island has blue eyes, it wouldn’t be out of the question to doubt the visitor.

    Another little monkey wrench would be if the visitor has blue eyes. The single blue-eyed islander might use the principle of generosity and think the visitor is referring to himself when he says, “It’s rare to see a blue-eyed person in this part of the world.” (Meaning, it’s rare for you brown-eyed islanders to see me, the blue-eyed visitor.)

    • Wyrd Smythe

      Hey, nice to see ya in these parts again; it’s been a while! I see you came wielding your logic axe! 😀

      You are quite correct on all counts. It’s a testament to flaws in how I stated the problem. I combined Munroe’s and Tao’s versions, and their respective versions handle your objections better.

      Munroe’s version has an island Garu (with green eyes), and that Garu only speaks one time (ever), and what the Garu says is, “I can see someone who has blue eyes.” In Tao’s version, the visitor is blue-eyed and remarks about, “how unusual it is to see another blue-eyed person like myself in this region of the world.” (I liked Tao’s visitor more than Munroe’s Garu, but the Garu has the advantage of implicitly speaking truth.)

      So, yeah, there’s a huge wide-open logic door in what I had the visitor say. 😮 I should have stuck with original! (Something about the wording bugged me, so I changed it. Mea culpa!)

      • rung2diotimasladder

        Haha…maybe it’s the nit pickers like me who are to blame for making philosophical writing so flat and tedious.

        Yeah, it has been a while! I’ve been meaning to get back to blogging, but there’s always some new hobby to jump into, or some other distraction. It’s getting a bit ridiculous.

      • Wyrd Smythe

        Well maybe your blogging season has passed. That happens; people just get their fill of something. I get that way about this blog sometimes — thinking maybe I’ve had enough. But then I take a break and find myself wanting to post something, so obviously I’m not done.

        It’s a hobby, so it’s entirely about what you want to do! 😉

      • rung2diotimasladder

        I guess I have multiple off seasons with just about all my hobbies. I do tend to come back to them at some point or another, with the exception of piano…at least so far. I actually have a gorgeous baby grand waiting for me in the living room. I’d say it’s a wasted luxury, but I do like the way it looks!

        Well, I’m not quite through with blogging. I’ve got a few posts on writing in the queue. After that, we’ll see.

      • Wyrd Smythe

        Oh, man, I envy you having, not just a real piano, but a (baby) grand. I love a grand piano!! (I’d have to count how long it’s been since I played one in decades. 😦 )

        Maybe blogging for you is like BOOL (a computer language I invented) was for me. Very on-again-off-again; periods of intensity with long bouts of ignoring it. This year I finally decided to bury it and move on. (That’s the first of a five-day “wake” series! 😀 )

      • rung2diotimasladder

        I don’t blame you for the envy. I felt that way about guitars…especially a certain Taylor. It really is a shame to waste such a lovely piano on me. I enjoyed listening to it when some musical friends from out of town came to visit.

        Yeah, blogging does seem to be that way for me. My problem is that I normally spend a lot of time writing, so by the time I’m through I don’t want to look at my computer anymore.

        I don’t know the first thing about inventing a computer language, but it sounds like it could be draining if done for prolonged periods.

      • Wyrd Smythe

        There’s a definite “if you like that sort of thing” aspect to language design. And I do, so normally it’s a lot of fun. But BOOL had design goals that conflicted, and I was never able to resolve them. An analogy might be of a mystery author who normally enjoys plotting intricate murder mysteries, but in one case had a grand idea about a murder but could never get the plot to work right.

        It’s sort of a case of working backwards from a desired end point, and sometimes the sad truth is, “you can’t get there from here” — no roads take you where you want to go. Ah, well, so it goes.

        I do know what you mean about computer time. My blogging goes down if I’m doing a lot of coding (for the same reason you cite). Or, if I’m doing a lot of blogging, I’m usually not doing much coding. Only so much time I can stand to spend sitting in front of the keyboard and screen!

And what do you think?

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: