MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can the well known blue eyed islanders puzzle be extended to an infinite number of islanders?

In that puzzle, a set of $k$ islanders, each with either blue eyes or non-blue eyes, each knows the color of every other islander's eyes but not his own. At time $t=0,1,...$ an islander who knows the color of his eyes raises his hand. Each islander can see which other islanders raised their hands at earlier times and nothing else. At time $t=0$ a visitor tells the islanders that at least one of them has blue eyes. All of the above is common knowledge among the islanders.

Suppose $k$ is finite, as in the initial version of the puzzle. Then, if all the islanders have blue eyes, they will all raise their hands at time $t=k$.

If $k$ is infinite, will they ever raise their hands?

I think it is best to assume here $t$ is an ordinal, and that each islander knows who raised his hand at any lower ordinal.

Certainly, if initially only a finite number of islanders have blue eyes, then after a finite time everyone will know his color. Thus, if initially they all have blue eyes, then after time $t=\omega$, it will be common knowledge that there are an infinite number of islanders with blue eyes. Unfortunately, that gets us nothing because I think this fact was already common knowledge at time $t=0$. I also considered maybe having the islanders collaborate on a strategy somehow - so long as they all know the others are using the strategy, and so long as it is still the case each only raises his hand when he knows his own eye color - but made no headway.

More speculatively, is there some kind of variant of this puzzle that could usefully distinguish between knowledge at transfinite times? I played around with different kinds of finite knowledge - maybe each islander can only see a subset of his fellows - but got nowhere.

share|cite|improve this question
2  
I doubt that this is possible, because transfinite ordinals differ from transfinite cardinals. The finite puzzle works because from each islander's perspective, the other islanders map naturally to an ordinal (the days), allowing the induction to proceed. But with a countably infinite population, there's no natural way for an islander to map the other islanders to a particular countable ordinal. You might be able to do something by putting the islanders into some kind of hierarchy, but then that breaks the symmetry that is such a pleasing feature of the original problem. – Timothy Chow Jan 2 '14 at 3:25
1  
To paraphrase @Timothy in his comment, the original riddle and its solution make use of the fact that the ordinal number of days is also the cardinal number of islanders. But once you enter the transfinite domain, not every ordinal is a cardinal. – Asaf Karagila Jan 2 '14 at 15:54
    
I suppose that is true, although perhaps a formal proof, to the extent possible, that no matter what the islanders agree beforehand noone will ever raise his hand, would be useful. Note that by time $\omega$ the islanders have solved the halting problem, and by higher ordinals they have solved much more. – user44653 Jan 3 '14 at 2:51

Here's my attempt to rigorously show that it cannot generalize. I originally wrote this for my blog, using the following formulation of the puzzle:

  • 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

The following solution works for infinitely many islanders, as long as only finitely many have blue eyes. I go into more information on my blog post, but since you already know the blue eyes puzzle you can probably prove the following.

Lemma 1 If an islander sees at least $N$ other islanders with blue eyes, she knows on Day $0$ that she will not be able to deduce her eye color before Day $N$.

Lemma 2 If an islander sees $N$ other islanders with blue eyes who are alive on Day $N$, then she can deduce her eye color by Day $N+1$.

Theorem 3 If there are $N+1$ islanders with blue eyes, they will perish at midnight on Day $N+1$, and all others will survive.

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 $N$ for all $N\in\{0,1,2,\dots\}$.

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 $\omega$. Will anyone wake up dead? The answer is of course, no. All islanders were able to deduce from the beginning that no one could perish after a finite number of days, so by the time Day $\omega$ begins, no one has gained information they didn't already have. We shall be able to extend this argument by transfinite induction to handle every ordinal (regardless of the cardinality of the ordinal or the set of blue-eyed islanders).

Theorem 4 If there infinitely many islanders with blue eyes, then no islanders can deduce their eye color by Day $\alpha$, where $\alpha$ is any ordinal.

Proof. If $\alpha$ is finite, we are done by Lemma 1. By transfinite induction, we may assume the theorem holds for all $\beta\lt\alpha$. In order to deduce her eye color by Day $\alpha$, $Alice$ requires new information on a previous day. However, by the induction hypothesis, $Alice$ knows from the beginning that every islander cannot deduce their eye color by a previous day. So, if $\alpha$ is a limit ordinal, we are done. The other case is when $\alpha=\beta+1$ for some $\beta\lt\alpha$. Alice wakes up on Day $\beta$, and is immediately bored. She already knew that everyone sees infinitely many islanders with blue eyes, so she already knew that everyone would be alive. Indeed, they are. So, she has gained no new information that morning, and therefore cannot deduce anything new by the end of the day, the beginning of Day $\alpha$. $\square$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.