Hacker News Reader

Comment by alwaysmetara | Hacker News Reader

The important point is that the outsider's comment "synchronizes" the islander's information. On Day 2, say you are a blue eyed person. You can see two other blue eyed people. Since these two people don't commit suicide during that day, you know there must be three blue eyed people with one of them being you.

So now you know your eye color.

View on HN

> you know there must be three blue eyed people

Why? The visitor didn't synchronize anything. All of the villagers already knew there was at least 1 blue eyed person. Per the story, 99 or 100 depending on your perspective.

Everyone commits suicide at noon in view of everyone else. So the lowest possible number of blue eyed people go up one per day.

Here's a longer explanation: Since people who know their eye color suicides at noon in plain sight of everyone else, we can set up induction.

If there's only one blue eyed person, they would suicide the first day at noon. Since everyone sees > 1 blue eyed people, they know this wouldn't happen. Since this doesn't happen, it's common knowledge that there is more than 1 blue eyed person. So if you only see one other blue eyed person, you must have blue eyes (but you don't know this yet because you see two blue eyed people).

On the second day, if there are only two blue eyed people, they would both suicide at noon. You see two blue eyed people. No one commits suicide because they either see two blue eyed people (if they have blue eyes) or three blue eyed people (if they don't). Now, everyone knows that there are more than two blue eyed people.

Since no one committed suicide the day before, you reason that there must be three blue eyed people, with the 2 people you see plus yourself. Thus, you know your eye color.

This is a bit long but I hope it's clear.

the argument i hear about induction is that it's only valid IF n=1 is a true situation, n=2 is a true situation, etc, up to n=k (where k is 100 here). But we are only given n=100, and we cannot say that n=1,2,3... is true. The best counter example is the surprise execution paradox: suppose you are a prisoner, about to be executed next week. However, a strange rule applies - if you are not surprised by the date of your execution, you get to go free. You reason that you cannot be executed on sunday, the last day, since by friday, you'd know, and thus not be surprised. by induction, friday is also not a possible day, since you'd know by thurs, etc. You conclude that you cannot be surprised, and this will not get executed. But come wed, you get executed, and is completely surprised!

This problem is different from the surprise paradox, which relies on probability changing each day, and a possibility that either (a) the executioner will be proven a liar by randomly guessing Sunday, or (b) you confidently guessing Wednesday and being right.

> Now, everyone knows that there are more than two blue eyed people.

That's incorrect, in a subtle way. The villagers (every single one) knew that before. It isn't discovered knowledge. Everyone (including the visitor) knows there are 99 or 100 because they can count them already, prior to the visitor.

So nobody is suiciding for 99 days. As an individual who sees 99 other blue eyes, why would you think or not think that you have blue eyes on the next day?

I meant strictly more, as in at least three. If you know that there are more than two blue eyed people and you can only see two, you know that you have blue eyes.

If you can see 99 blue eyes, you know that all the other people see either 98 or 99 (if there's a total of 99 blue eyes) or 99 or 100 (if there's 100 blue eyes). However, if some people see 98 and know that there's at least 99 people with blue eyes, then they would all suicide. Since they don't, you know everyone sees either 99 or 100 blue eyes. Since you see 99, you must have blue eyes.

As a villager, you already know everyone sees either 99 or 100 blue eyes. You see 99, but you don't know if everyone else sees 99 or 100 (if they have blue it's 99 if they dont it's 100). You knew it before the visitor, and after his statement.

This does not help in deducing if you have blue eyes.

> then they would all suicide

No they wouldn't. Nobody should suicide at all. The visitor saying someone has blue eyes, was already known by every member of the village and every member of the village saw more than 1 person with blue eyes prior. Nothing is different because he said something.

> Since you see 99, you must have blue eyes

I don't know there's 100, so I don't know I have blue eyes.

This is a solved problem. When a proof is written, you should challenge the proof, not just reassert your intuition.

You are ignoring islander A's view of B's view of C's view of ... Z's view of situation.

Think about 3 islander's, where A thinks "if I have green eyes, then B and C are in a situation equivalent to me not being here, and B sees exactly 1 blue eyed person C, and B knows that 'C sees 0 or 1 blue eyed people, but then C learned that 0 is impossible'"

Is the outsider not needed for this line of reasoning to work assuming that the total number of people doesn't change? All the 100 blue eyed would commit suicide after a hundred days after the creation of the island since they work out they have blue eyes. I think the main challenge in this puzzle is the lack of assumption on what kind of reasoning the islanders are capable of doing and what the initial conditions are.

The problem is the initial leap of logic - why should any tribe member think that the foreigner is talking about them at all? The foreigner says 'there are other blue-eyed people' and everyone can see that there are indeed other blue-eyed people. There's no reason for anyone to think that they might be in the blue group.

If there was some reason to start a count, sure, but there isn't. The foreigner just states that there are other blue-eyed people, which the tribe already knows.

Reduce the problem to 2 blue-eyed people and it should be more clear. If Alice and Bob are the only people with blue eyes, then yes, Alice might think that the speaker was only talking about Bob. But when Bob fails to sacrifice himself the next day, that must be because he also sees a person with blue eyes, and that can only be Alice.

It's different with only two people than it is with multiple. When there's only one other person and they don't act the next day, then the logic works. But when there are numerous people and there is no reason to start counting, then it doesn't extrapolate out.

Put more clearly: Foreigner says "blue eyes!". n is 2. If you have blue eyes and you don't see the other blue-eyed person top themselves, you conclude that you also have blue eyes as does the other person, and it's belly-opening time.

But when n is 100, that initiation is missing. No-one tops themselves the next day? Hardly suprising - there are a hundred of the buggers. There is no reason to start counting, no "hang on, why didn't ol' blue eyes over there kick the bucket?".

And, given that these are humans and not cronjobs, no-one is going to be patiently waiting day in, day out for 100 days to see when they'll all kill themselves. Drama can't even fester, since the tribesfolk are forbidden from talking about the issue. Life goes on, and over three months later, the foreigner's statement wouldn't cause a bloodbath :)

TL;DR: if you want to make a fancy logic puzzle, don't use 'humans with bizarre rules' as your subjects. :)

You aren't applying all possible logical reasoning about the situation (such as the characters recursive mental models of each other's mental models), unlike the hypothetical completely rational characters.

I think you've missed my point. At low n, yes, that recursion works. But once you get to the point where you can see that each [other] blue-eye can see multiple blue-eyes, there's no real reason to start counting. There's nothing to logically deduce if the people aren't mentally counting, as keeping that mental count is a fundamental part of the algorithm. If n is 7, for example, then a blue-eyed tribesperson would see that the other blue-eyes can see [at least] the remaining 5. And as such, there is no reason to start counting. There's no "hey, that guy didn't do anything!" to start the process going, as there would be with low n. The algorithm is separated from it's starting conditions.

Also, the characters are definitively not 'completely rational', as they're also described as being 'devout' :)

Why can't they synchronize at any other moment? They already knew N is either 99 or 100 even before the visitor came.

Consider the case of 2 blue eyed people, Ben and Betty. Everybody knows there is at least one blue eyed person. But does everybody know that? That is, does everybody know that (everybody knows there is one blue eyed person)?

From Ben's perspective, Betty might be the only blue-eyed person, so Ben does not know if Betty knows there is at least one blue eyed person. This is important because Ben needs to correlate Betty's actions with her knowledge; he can't do that if he doesn't know what her knowledge is.

After the traveler's announcement, Ben knows that Betty knows there is at least one blue eyed person. This is the new information.

And with three people, we add another layer: Ben does not know if Betty knows that Bobby has blue eyes. And so on.

The visitor's announcement is special because it is infinitely layered. Everyone knows one person has blue eyes, and everyone knows that everyone knows, and so on, ad infinitum. This is called common knowledge: https://en.wikipedia.org/wiki/Common_knowledge_(logic)).

Though to be fair, this isn't explicitly stated: the traveler "addresses the entire tribe" but it's critical that everyone in the tribe knows this is common knowledge. Merely addressing the entire tribe is not enough: if the traveler's announcement was in the form of a BCC mass mailing, there would be no new information and so no suicides.

It isn't infinitely layered! It is N-layered, which is critical.

"synchronize" is a bit vague. It can be made more precise. Simply put, it sets the initial condition in the recursion. Before someone says "there is a blue eyed person here", the initial condition in the recursion does not hold. The islanders are not allowed to say it so the visitor was the first one to make the statement. If indeed one of the islanders said it (whether blue or brown eyed) the condition would hold as well and the recursion would follow too. However none of them can talk about it.

Reply on news.ycombinator.com