Comment by lkozma | Hacker News Reader

Comment by lkozma | Hacker News Reader

Parent Full thread

Solution 2 is correct, Solution 1 is wrong because there is always transfer of information in the stranger's speech.

Suppose there was only 1 blue-eyed person:

  [before]: Not everyone knows there exist blue eyed people 
  (the blue eyed person doesn't know it)
  [after]: Everyone knows there exist blue eyed people.

Suppose there are 2 blue-eyed persons:

  [before]: Everyone knows there are blue eyed persons.
  Not everyone knows that everyone knows that there are blue eyed persons 
  (the 2 blue eyed don't know). 
  If Alice and Bob are blue eyed, Alice knows Bob is blue eyed, 
  but thinks that Bob thinks nobody has blue eyes.
  [after]: Everyone knows and knows that everyone knows etc.

Suppose there are 3 blue-eyed persons:

  [before]: Everyone knows there are blue eyed people.
  Everyone knows everyone knows there are blue eyed people.
  Not everyone knows everyone knows everyone knows there are blue eyed people.
  This last statement changes after the speech.

Similarly for any n:

  [before]: (everyone knows that)*(n-1) there are blue eyed people.
  [after]: everyone knows everything.

EDIT: reworded for clarity.

Incidentally, this is why dictatorships don't allow gatherings of people (or free broadcast media). Everyone knows the regime is bad but not everyone knows that everyone knows etc. When the whole hierarchy collapses, revolutions break out.

I understand the logic behind the solution and it makes full sense to me. What I still struggle with is: what specific piece of information is being passed by the foreigner. I get that it is "everyone knows everything" but for n > 1 everyone already knew the specific fact that was being communicated. What is special about the announcement that drives it? It seems like it is actually "the timer starts now!"

The specific information which was not known and is known after the foreigner's speech is that "everyone knows that everyone knows that everyone knows that (repeated n or more times) there are people with blue eyes." This was known only up to n-1 repetitions. To infer this new statement, the islanders have to be aware that the others are listening, they understand, they know that everyone understands, etc. etc.

To infer this new statement, the islanders have to be aware that the others are listening, they understand, they know that everyone understands, etc. etc.

That's deeply unsatisfying because we are told that everyone is capable of making the observation that is communicated right from the beginning for n > 1. What prevents the group from acting as soon as the situation starts but before the foreigner speaks?

The message adds information to the system but it is not that there is one person with blue eyes, i.e. what was explicitly stated. I think it adds information about the time at which an action will or will not occur. The information passed is "you can expect something to happen to the people with blue eyes tomorrow."

The case with 3 people always bugs me in solutions for this puzzle: If Alice, Bob, and Carol have blue eyes how can they not know that everyone knows that there are blue eyed people?

They know that everyone knows that there are blue eyed people.

What they don't know is that everyone knows this. In other words, they don't know that everyone knows that everyone knows that there are blue eyed people.

Alice thinks like this:

1. there are blue eyed people (e.g. Bob and Carol)

2. everyone knows there are blue eyed people (Bob can see Carol, Carol can see Bob, everyone else can see them)

3. I know that 2 is true, but Bob and Carol might not know. Bob might think that Carol thinks that there are no blue-eyed people. (Of course, in reality, Bob does not think this because he can see Alice as well)

Thanks. That was very helpful. Its easy to see but somehow hard to believe that this applies to 4 people as well (now everyone can see 3 blue eyed people) etc.

Reply on news.ycombinator.com