Damien Katz

The eye colour will make no difference to the tribe, however having a Brit arrive (not mentioned in the question, but obviously a Brit) to colonise the country is going to have an effect. Within two years regardless of eye colour they will be playing cricket, drinking tea and singing God Save the Queen.

I think it's flawed, too. Based on the logic trail they should all commit suicide.

Great riddle. And you are probably wright.

Core of their inductive argument at wiki was that "Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does not know that the other blue-eyed person has this same knowledge.". Flawed. Everyone can see other ppl`s eyes and everyone knows that others see everyone elses eyes (they are just prohibited from talking about it). Unless they wanna argue that villagers are incapable of deducing the fact that other villagers can see, but are capable of deducing their "answer".
So when you have 100 blue-eyed ppl every1 of them sees 99 other blue-eyed ppl and figures "if only you ppl knew" and maybe "you have same eye color as that Brit" :)
It all comes down to fact that to kill himself villager has to be 100% sure of his eye color. He cant be 100% sure of his blue eyes if he sees 99 blue-eyed and 900 brown-eyed ppl walking around.
He doesnt know the "stats" for eye colours in village and to top it of: "The tribe consists of 1000 people, with various eye colours.". For all he knows he could be the only pink-eyed person in the village :)

Goedel's theorem is inapplicable here, since it only applies to logic systems which can express enough arithmetics. And the islanders don't need that amount of arithmetics to reach their conclusion.

well it seems a fairly poor system of ethics by which to run a society, maybe with time they will discover that strange women lying in ponds distributing swords is a much better basis for a system of government. Anyhow, the induction is flawed. For n=1 you have everyone wandering about in blissful ignorance of their eye colour. One person knows there is zero or one blue eyed person. 999 people know there is one or two blue eyed people. The visitor arrives, puts foot in mouth and adds new information to the system. Next day the solitary bluey goes to the square and does the decent thing because his possibility of there being zero blue eyed islanders has been ruled out. The following day nothing happens. The other islanders now know that there are either zero or one blue eyed people left. They do not all fall upon their swords like suicide squad of the "Peoples Liberation Army of Galilee".
In the case of n=2 you have 2 people who think that n is either 1 or 2 and 998 people who think that n is either 2 or 3. The visitor announces that there is a blue eyed person. Nobody is given additional information. Nobody dies (unless they all decide to tuck into a hearty "long pig" stew.)

> And the islanders don't need that amount of arithmetics to reach their conclusion.

But how do you know they don't have some other, more advanced logic system that allows them to deduce a answer faster? After all, they are highly logical. Can it be proven they don't have such a system?

then again . . . I might change my mind. When n=1 There is new information on day 2. The other islanders now have a perspective of what the first islander could see. I am not quite ready to go with the induction argument yet though. For n=2 nobody dies the first day, but when nobody dies then the 2 people know that n is not 1 therefore they top themselves. For n=3 . . . ah shucks maybe they do all die. Blues first because there are fewer of them, followed by browns. The visitor has not added information to the system, just given them a point in time to count from.
Religion sucks.

It took me a while to grok the solution. Anyway, I posted my thoughts on http://blog.perfectapi.com/2008/02/difficult-blue-eyes-logic-puzzle.html

The question is indeed flawed in the version you posted. Not to mention bloody. Wikipedia uses the phrase "perfectly logical". Perhaps that would satisfy your logic requirements.

> For n=2 nobody dies the first day, but when nobody dies then the 2 people know that n is not 1 therefore they top themselves.
This is where i found fault. Perhaps it is because of the phrasing of the riddle but why should any1 expect that other tribe members have come to the same conclusion/answer?! If we are talking logic then thought process of other living ppl is unpredictable and sometimes unreliable. In reality the chance of other blue-eyed person being "slower" is still present and therefore voids placing yourself at top.

As for the browns going straight after them: They dont know that only other eye color on the island is brown. Any brown-eyed person after the "departure" of blue-eyed people still has no way of knowing that he is brown-eyed.
>He doesnt know the "stats" for eye colours in village and to top it of: "The tribe consists of 1000 people, with various eye colours.". For all he knows he could be the only pink-eyed person in the village :)

Wow, interesting post. I like your allusion to Gödel and agree with you for the same reasons.

Godel's theorem doesn't apply here though. The theorem applies to certain axiomatic systems and it says that unprovable statements can be constructed in those systems.

Here, when it is said the islanders are logical, it doesn't mean they have a complete axiomatic system. It simply means that given some claims, they can deduce the necessary implications of those claims. That's all that's required to make the puzzle work.

As an example, if I gave you two premises of a syllogism like "Socrates is a man" and "all men are mortal," if you are perfectly logical, you will deduce the implication "Socrates is mortal." You don't need to bring up anything about axiomatic systems in which liar paradoxes can be constructed (as with Godel) to be able to deduce this conclusion.

AL:
1. What is the shortest amount of days you can figure out your color, is there a shortcut? If every blue-eye person can see N-1 blue people, why do we have to wait N days before we decide? Why not just one day? Why not instantly? Can it be proven this *cannot* be done faster?
2. If its not provable what's the fastest way, but we do know the way we found, how do we know the other blue-eyed islanders found the same way we did? The induction proof requires everyone uses the same method. Perhaps there are infinite logical methods of deducing the answer, with different days the eye color would be discovered. Maybe they found a faster one, maybe they found a slower one. How do we know we found the same one as the other blue-eyed villagers?

Sorry to nitpick but I study logic (graduate student in mathematical logic) so I can't help myself. In particular I object to the characterization (and relevance) of Godel's theorem as showing there is no perfect system of logic. In fact it does nothing of the kind. Rather what Godel's theorem shows is something much subtler.

Godel's first incompleteness theorem shows that if a mathematical theory strong enough to represent arithmetic is axiomatized IN FIRST ORDER LOGIC in a way people could grasp (technically that it is axiomitized in such a way that one could in theory write a computer program to list off the axioms and assuming people are turing machines...) then there is a statement of the theory that is 'true' but not proveable. This statement only really shows that first order logic doesn't allow one to capture the notion of finite because technically there are models that satisfy all the axioms that cause the statement to be false (they just believe in infinite numbers). Alright it gets a little complicated there but the point is that this specifically refers to certain kinds of logics and it merely shows that certain concepts can't be capture by them.

----------

This having been said I think you are correct that the problem is underspecified. In particular to make the problem really well defined you would need to explain exactly what sort of system you took the natives to be reasoning in so forth and so on.

Still I think it likely that in most reasonable preciscifications the solution where the natives kill themselves would be correct. Why? Because it's false that the natives learn nothing new at this point. They learn that every other native was told at a particular time there was at least one blue eyed person on the island.

This may seem like nit picking but just consider the case for n=2. When told that there is at least one blue eyed person on the island (which both blue eyed people already know) they also learn that EVERY OTHER PERSON ON THE ISLAND KNOWS THERE IS AT LEAST ONE BLUE EYED PERSON. Hence this is what allows both of them to conclude that they must be blue eyed after the first day passes. When we go to n=3 the situation is a bit more complicate but we can state what is learned as this, "If there are only two blue eyed people on the island they both learned that there is at least one blue eyed person on the island." Of course it gets more complicated as n increases but there is always a piece of information conveyed.

Also I don't see the issue with whether they use the 'same' reasoning method. They just need to be good enough at logic that they all realize this particular argument within a day.

Here are my thoughts: Flawed question because it does not specify there are only two eye colors. Assuming that is clear:
If there is only 1Blue, he kills himself. The others then know they must have brown, or else the initial suicide wouldn't have happened. So they all die by day two.
If there are two blues, nothing happens the first day because each is waiting for the other to commit suicide. Once they realize that, and cannot see another blue, they know they have blue also. So they both die the second day, and on the third the tribe realizes they must all have brown and they kill themselves too. Using this same logic you could progress all the way to 100 blue eyed people dying on the 100th day. And on the 101st, all the browns would realize they had brown and bite the bullet also.

However, the flaw in that logic is this: The visitor introduced no new information. Everyone on the island knew there was brown and blue before they came. So why would anything change? The only options, depending on which 'puzzle options' you believe are that no one dies or everyone dies in 102 days.