From: hiraga@Csli.Stanford.EDU (Yuzuru Hiraga)
Subject: Re: The Last Word on Brown Eyes, Blue Eyes (NOT!)
Organization: Stanford University CSLI
Distribution: world 
Date: Sun, 27 Sep 1992 01:59:44 GMT

# This thing is beginning to be more a matter of psychology
# than math or logic...

First of all, let's straighten up what the obstacles are.
# Allow me the use of the word "obstacle": I'm speaking from the
# position that the problem is valid.

A. The foreigner's comment ("there exists a blue-eye") adds no new
   information to the situation.
  This can be further divided into two cases:
  A1. The comment states an already prevalent knowledge, so nothing happens.
     This seems to come from people who are less familiar with the problem.
  A2. The comment is irrelevant, and the "immediate-suicides" should have/
      could have taken place much earlier.
     This comes from people quite familiar with the problem (or its
     variants), including Chris Long.

B. The induction doesn't work
  The cases for n=1, 2 (,3) does not generalize to all n (in particular,
  n=300) -- the induction breaks down at a certain n.
  This objection is understandable, since there do exist puzzles that
  take advantage of such breakdown.

C. Minor pitfalls/shortcomings in the problem statement
  Do all the inhabitants reason logically?
  Do they all know others can reason logically?
  Did they all hear the foreigner's comment (within the same day)?
  Do they all know that the others heard it?
  etc.

In what follows, I shall make a general comment on A. (encompassing both
A1. and A2.), and discuss A2. in detail.
I will not make extensive comments on A1., B., or C.; since these
have been addressed in previous postings (including mine, for A1. and B.).
As for C., everything will be interpreted in favor of the problem's intent.
And since the existence of brown-eyes plays no essential role in the
problem (and solution), I'll not bother mentioning them and focus
on the blue-eyes.

# Though, of course, all questions on the above points are welcome.

===========================================================================

The critical point is whether the foreigner's comment "there exists a blue-eye"
adds any essential information or not.  My answer is yes.
This information, in a nutshell -- is the knowledge that "everyone knows
there exists a blue-eye", or rephrasing it, the fact that "everyone knows
that everyone knows that there exists a blue-eye."
This, of course, is not the same as the fact that "everyone knows there
exists a blue-eye" (or is this obvious to all? At least it would be,
for the advocates of modal/intentional logic).

But this by itself is rather far fetched.  Its effect is as follows:
Although everyone (that is, every blue-eye) knows that there are either
299 or 300 blue-eyes (depending on whether himself is blue or not),
one does not know which is the case.  Rephrased, he does not know whether
others are seeing 298 blue-eyes or 299 blue-eyes.  The foreigner's comment
has the effect that (after 300 days of time), it can be deduced that
the former is not the case.  And without the comment, this would have
been impossible.

For later convenience, let's call this as the "common-knowledge" information.

===========================================================================

I'll not repeat arguing why this is the case, but rather proceed directly
to A2., in particular, Chris Long's comments.

In article <Sep.26.08.07.59.1992.24360@remus.rutgers.edu> clong@remus.rutgers.edu (Chris Long) writes:
>The reason the original statement of the problem is flawed is
>that it specified that the those who found out they had blue
>eyes would immediately kill themselves, and this was in effect
>previously.  In the rec.puzzles FAQ, no person takes any action
>until a certain point (initiated by an outside element, a preacher
>in this case).

In short, his (or her? excuse me if I'm wrong) point is that
the initiation of the "immediate-suicide" condition (so to speak)
is the key factor in triggering any action.  In doing so, he also
claims that "common-knowledge" mentioned above is irrelevant.
This is directly opposed to my claim that "common-knowledge" serves as
the real trigger, and "immediate-suicide", although of course necessary,
can be prevalent with no effect by its own.

Since he says:
>For a better statement of this puzzle which avoids this problem see
>the rec.puzzles FAQ.

let's look into the problem from two sides, whether the blue-eyes
will voluntarily commit suicide in our problem, and what's the
difference with the FAQ problem (logic/smullyan/priest.p).

At this point, I regret that Chris didn't include his own solution
in his posting... had he done so, things would have been more easier.
Here's my try.

Take the simplest case that there are only two blue-eyes.
By looking at each other, they both realize there does exist a blue-eye
(namely, the other).  Can they deduce from this that the person himself
is blue-eye?  No. One can assume himself to be brown-eyed with no violation
of the problem conditions.  Can they somehow inform the other to be a blue-eye?
No, that's against the problem condition.  This is as far as I can get.

On the other hand, adding the "common knowledge" is indeed fatal, as
(repeating this for the N-th time):  "Suppose I'm brown-eyed.  Then he,
seeing a brown-eye, AND KNOWING THAT THERE EXIST A BLUE EYE,
will immediately deduce that he's blue-eyed..."
The same goes for cases of three or more blue-eyes (details omitted).


And now let's look into the FAQ problem (I'll not include the whole text
to save bandwidth and extra reading: see FAQ part 13/15 of rec.puzzles
or the posting of this particular problem, both by Chris Cole).

Observing the problem, we find the problem is indeed as Chris states,
but at the same time, is actually more "flawed" than our problem at hand.
The reason is as follows.
The crucial lines in the problem are:
 >He[=the priest] announces in Mass one Sunday that the spouse of each
 >adulterer has the moral obligation to punish his or her adulterous
 >spouse by publicly denouncing them in church, and that he will make
 >time during his next Sunday service for this, and continue to do so
 >until all adulterers have been denounced.

Here, the priest does not explicitly mention (his knowledge of)
the existence of an adulterer (our "common-knowledge").
However, looking at the solution, we find that this is implicitly
assumed:
>Let's start with the simple case that N = 1.  The offended spouse
>reasons as follows: the priest knows there is at least one adulterer,
>but I don't know who this person is, and I would if it were anyone
>other than me, so it must be me.
 ....
>What happens if N = 2?
>...
>But if they do not
>think they are victims, then they must think there are no adulterers,
>contrary to what the priest said.
 ... etc.

See?  It is taken for granted that the priest admitted the existence
of an adulterer, and the whole reasoning depends on that.
Suppose the priest had said "I won't say whether there are any adulterers
among you or not, but had there been one, then...[the rest as above]".
Then the above solution will immediately break down.

So the "common-knowledge" IS essential in this problem as well,
and together with the earlier claim that "immediate-suicide"
by itself is not fatal, my point is concluded.

-Yuzuru Hiraga

# Note: crosspost to "comp.theory" has been deleted on
# request, thus overriding Chris' Followup-To line (I wonder why he 
# did this).