I was asked by my friend and colleague Dr. Stephen “Danger” Ware on a Facebook post about another interesting puzzle concerning infinity if the Blue Eyes Puzzle could be extended to an infinite number of islanders. Intuitively, it seems reasonable that the solution should generalize nicely: if there are infintely many pairs of blue eyes, it will still take “infinitely many days”. But, these things can be subtle once infinity is thrown into the mix, so I thought it’d be fun to attempt a rigorous treatment of the question.
First things first, I’m going to reformulate the puzzle to avoid the words “everyone is a perfect logician”, which for some reason bugs me more than dealing with infinity or islanders who cannot communicate with each other.
So, suppose there is an island with several inhabitants. These islanders cannot communicate with each other, but they share a few truths:
- All islanders are immortal, except as explained below.
- All islanders know the color of every other islander’s eyes, but not their own.
- If an islander has enough information to logically deduce the color of their own eyes, they will perish at midnight of the following day, which will be noticed by the other islanders.
- Any message washed ashore in a bottle can be trusted.
Now as it happens, at 12:01am on Day 0, a message washes ashore in a bottle, and is read by all the islanders:
There is at least one islander with blue eyes.
What happens?
Finite solution
Of course, since it wasn’t specified, you would reasonably assume that there are only finitely many islanders. But, in fact, the following solution works for infinitely many islanders, as long as only finitely many have blue eyes.
The easy case is when there is only one islander with blue eyes. She reads the message, looks around, and sees no one else with blue eyes. Therefore, she correctly deduces she must be the islander with blue eyes. So, at midnight on Day 1, she’s dead as a doornail.
What about the rest of them? Well, suppose you are another islander. You may be right to fear that you have blue eyes when that message arrives. However, you saw at least one other person on the island who did have blue eyes, which means that the message told you absolutely nothing new about yourself. Importantly, you have no other way of gaining more information except by observing when other islanders perish or survive on following days. Thus, you will not die on Day 1.
Now, when you see the blue-eyed islander pass away at noon on Day 1, her passing is itself new information. Putting yourself in her shoes, you realize that if you had blue eyes, she’d have been in the same position as you were the previous days, and would have lived just as you did. Alas, she did not, so you conclude she saw that your eyes were not blue, and since they could be any other color, you rest easy with the lack of knowledge. Thus you, and every other islander, live on.
So, we have proven the following fact.
Proposition If there is only one islander with blue eyes, she will perish at midnight on Day 1, and all others will survive.
However, we are more interested in the lemmas which led us to this conclusion.
Lemma 1’ If an islander sees at least one islander with blue eyes, she cannot deduce her eye color by Day 1.
Lemma 2’ If an islander sees no other islanders with blue eyes, she can deduce her eye color by Day 1.
We’d like to prove two generalizations. We will always assume
Lemma 1 If an islander sees at least
Proof. This is trivially true for
Since
Lemma 2 If an islander sees
Proof. We again proceed by induction as this holds for
It’s interesting that I used contradiction above. It would seem that Alice must assume the Law of the Excluded Middle here, but I am not a logician, so perhaps I missed something.
Theorem 3 If there are
Proof. Each blue-eyed islander sees
What’s the wait for?
It’s worth pointing out that when there is more than one islander with blue eyes, no one gains information from the message on the bottle. So, what’s the hold up? It wasn’t obvious to me from the above proof (even though I wrote it!), so here’s my intuition.
The important thing to note is that if you see
The infinite case
So, we’ve handled the case where there are an arbitrary number of islanders (even infinite!), but only finitely many islanders with blue eyes. So, what if there are infinitely many islanders with blue eyes?
Well, we already have a very nice lemma above, Lemma 1. That allows us
to prove that, since all islanders see infinitely many pairs of blue eyes,
no islander can deduce their eye color by Day
So, assuming that our days are limited to the finite ordinals, the case is closed. But why should we stop there? What if there exists a day for every ordinal number?
We should consider what happens on Day
Theorem 4 If there infinitely many islanders with blue eyes, then no islanders
can deduce their eye color by Day
Proof. If
In conclusion
In working on this article, I was particularly amused by the following:
- If the cardinality
of islanders with blue eyes is finite, then all blue-eyed islanders will perish after finitely-many days. (Specifically, -many.) - If the cardinality
of islanders with blue eyes is infinite, then all blue-eyed islanders will remain alive no matter how many days pass, even after -many days.
I have some intuition here: in any case, the unknown datum for each islander (their own eye color) is finite. Thus, if there are finitely many blue-eyed islanders, this datum is important! But, if there are infinitely many blue-eyed islanders, then the status of an islander’s own eyes is irrelevant to the cardinality of that set. Therefore, the bottled message, which says that the cardinality of blue-eyed islanders is positive, gives no new information to the islanders, because they already have exactly the same information about the cardinality of blue-eyed islanders.
I hope you found all that interesting. If you have any comments or questions, shoot them to me at @StevenXClontz. Thanks for reading! :-)