The Problem
There are variations to this problem, but we will go by the XKCD version discussed in www.xkcd.com/blue_eyes.html. It goes:
“A group of people with assorted eye colors live on an island. They are all perfect logicians — if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.”
“On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.”
“The Guru is allowed to speak once (let’s say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following: ‘I can see someone who has blue eyes.’”
“Who leaves the island, and on what night?”
The Traditional Solution
The traditional/standard/irrefutable solution is described everywhere, including in xkcd.com/solution.html. Basically, if there were only one blue-eyed monk (BEM), then he wouldn’t see any. He would realize he must be it, and leave that night. If there were two, they would each see only one and would assume the other guy would leave that night. When they saw each other the next day, they would both leave. And the people who were worried that they might be Number 3 would all breathe a sigh of relief. And so on. For the case described above, all 100 would leave on Night 100.
Disclaimer (and Personal History)
There is a reason why I was never invited to Logical Island. When I first read this problem, decades ago, I didn’t even figure it out on my own. I cheated and read the solution. But then I thought, “That’s pretty slick”! When I ran across the problem again, a decade or two later, I remembered the answer and still thought it was pretty cool. But I thought it was too bad that there wasn’t a quicker solution. The third time I ran across it, another decade or two later, I became obsessed with finding that solution. It wasn’t going well, but a few nights later it occurred to me that the answer might involve modular arithmeticExplained. A test using Mod 6 was effective.
The next logical question would be “Why is six so special?” If all of the monks can’t agree on the same base/modulus without communicating, the scheme fails. When I introduced my idea on a different forum, one commenter quipped (sarcastically), ‘if that scheme is even legal, what’s to stop you from just having everyone who sees an even number of BEMs go to the ferry on Night One?’
I thought that was way too extreme, but as I was typing “ridicul . . .”, a bell went off in my head. Of course. That’s it! Mod 2. But that commenter wasn’t buying it.
The Fastest Answer
In my plan, everyone who sees an even number of BEMs (remember, zero is an even number) goes to the dock the first night. If when they got to the ferry, everyone else there had blue eyes, they would all board the ferry. Otherwise, having non-blue eyes, they would all quietly return home. If the problem isn’t solved that night, everyone that sees an odd number of BEM’s (everyone else) leaves on the second night.
Let’s say there were 99 BEMs (or 101). They would all see 98 (or 100) BEMs, and they would (as in the case of one BEM) get on the ferry the first night. That would be that. But if there were 100 BEMs, those seeing all 100 would all go to the ferry the first night. They see nothing but non-BEMs and all go home quietly. The next morning, those seeing 99 and hoping that those seeing 98 acted accordingly, would realize that wasn’t the case. They would all leave that second night (as in the two BEM case). End of story.
Advantages
If there are 200 monks between the ages of, say, 19 and 85, with minimal turnover, you can expect three deaths each year. That means there is about a 50% chance that the number of BEMs will mysteriously change while the 100-day clock is ticking. (I’ve heard no discussion about how the traditional method handled such things. But a similar situation is addressed in the next-to-last paragraph [Go]). My new method virtually eliminates that possibility. Even if nobody dies, there is over three months of meticulous counting that can be avoided.
Other Concerns and Considerations
More About the Technique
As we’ve discussed, this method is actually based on the traditional method, but folds the number/time line into the smallest possible segments using modular arithmetic. For a monk that sees 100 BEMs, there are only two possibilities. Either there are 100 BEMs (which all see 99) and he is among the 100 others, or he is one of 101 BEMs. Nobody seeing 100 thinks there might be 102 or 99. If you see 100 and think you might be one of 101, then you don’t care what the non-existent monks that see 102 BEMs think. For those seeing 100 BEMs, this scheme folds the other monks from both possibilities – those seeing 99 and those seeing 101 – into heading to the ferry the same day.
As mentioned, the solution must be so logical as to be adopted unquestionably by all monks without discussion. First, remember that they were able to come up with the original method without discussion (something I couldn’t do). Why would they stop at the first answer they came up with when they can clearly see the disadvantages to that approach. This answer adds another simple mathematical concept for the next logical step. But if you know of another logical solution candidate, even completely unrelated to these techniques, speak right up.
I mentioned that there are variations to this puzzle. This technique would not work in variations that require the monks who discover their eye color to quietly commit suicide in their homes. And it is the ferry part, not my new technique, that would minimize the damage of an oracle mistakenly (or maliciously) claiming he saw a BEM when there were actually none.
Questions Answered
Even if based on the original method, doesn’t the mod 2 math allow two possible answers? Why wouldn’t they have those seeing an odd number of BEMs go first? Because the “let odd go first” plan is not the direct result of simple mod 2 math. And the first two cases (1 and 2 BEM’s) in my technique are exactly the same as the original method.
I’ve heard that the inductive method proves that the original technique is the only one possible. Nonsense! All mathematicians know there are commonly more than one way to solve or prove anything. Just a couple years ago, two teenage girls found a new trigonometric proof to the Pythagorean TheoremArticle.
I’ve heard that these monks are illegally communicating information. No, they are giving the same information at night as they were giving during the day – no more information than in the original approach. In either case, when the lone BEM disappears the first night, he is telling every other monk (that was worried that he might be Number 2) that they can stand down.
But what would happen if some of the monks stuck with the old technique? Well, I guess all monks weren’t perfectly logical. But if there were an odd number of BEMs, for example, and only some of those seeing an even number go to the ferry, as my plan dictates, then they would see other BEMs and leave as required. The next day, those who chose the traditional solution would notice that there were far fewer BEMs. Regardless of whether the new number of remaining BEMs was odd or even, they would realize what happened and leave the next night.
(If they still couldn’t figure it out, they could at least proceed with the traditional plan using the new BEM count at the original starting point. [Return to Advantages]
Would they be allowed to take action without knowing their eye color? Nothing in the rules restricts their access to the ferry dock or prevents them from noticing the eye color of those they meet. I would expect logical monks to be curious and willing to conduct simple experiments that could benefit themselves and the group.
Any questions?
