Blue-eyes logic puzzle

Factual Questions
21

All 100 leave on the 100th day. This is because only then do any of them know that he himself (or she herself) has blue eyes–and on that day, all of them know this.

In other news:

I know how to say what new information people on the island have after the Guru speaks in the case where only two have blue eyes. (Namely, the new information is: “Now the other blue eyed guy knows that at least one person has blue eyes.”) But I haven’t worked out how to formulate the corresponding piece of new information in the 100-blue-eyed-people case much less the 3-blue-eyed-people case. Just keeping you posted… :stuck_out_tongue:

22

It’s not one person leaves per day, no one leaves until the 100th day, when all 100 blue-eyed people leave. On that day every blue-eyed person simultaneously says, “I have inferred that there are at least 100 blue-eyed people on the island, and I only see 99, so the 100th must be me”.

23

It’s similar, but it gets pretty wordy. For 3 blue-eyed folks, it’d go something like “Now the other blues know that the other blues know that at least one person has blue eyes”. For 4 blues, it’d be “Now the other blues know that the other blues know that the other blues know that at least one person has blue eyes”. And so on.

Really, this problem is a poster child for the method of mathematical induction.
Proposition P(N): “For any N >= 0, if there are N blue-eyed islanders, then on night N, all blue-eyed islanders will leave”
Foundation: If N=1, then the single blue-eyed islander will know that he must be the blue-eyed guy, and leaves on night 1. Therefore, P(1) is true.
Increment: If P(N) is true, then on day N+1, every blue-eyed islander will know that there are at least N+1 blue-eyed islanders. If there are exactly N+1 blue-eyed islanders, then each will only see N, and each will know that he himself must be the N+1th. Therefore, each blue-eyed islander will leave on night N+1. Hence, if P(N) is true, then P(N+1) is true.

We’ve now established that P(1) is true, and that if P(N) is true, then so is P(N+1). The result follows by induction. Quite Easily Done.

24

It’s a lot simpler than all the algebra and stuff implies.

If 100 islanders have blue eyes, everyone with blue eyes sees 99 islanders with blue eyes. If, on the 99th day nobody has left the island, everyone who only sees 99 pairs of blue eyes realizes there are in fact 100 pairs of blue eyes, and now knows their own eye color. They may all leave the island at the same time.

25

Actually, now that I think about it, the puzzle doesn’t seem to work. If there are 2 people with blue eyes, and each day the guru says “I see someone with blue eyes,” how do either of the two people with blue eyes know whether the guru sees the same person they saw yesterday? Saying “I see someone with blue eyes” on Tuesday doesn’t give any more information than it did when you said it on Monday, because you could be seeing the same person!

26

Why could a blue-eyed person think this but not a brown-eyed person?

27

Here’s a similar (in fact, identical, except in wording) problem, which may be instructive:

There is a certain archipelago, consisting of 2^3 many islands, arranged into the vertices of a 3-dimensional cube. There are also bridges between islands, corresponding to the edges of this cube (so each island has 3 bridges out of it).

On each island, there is a sequence of bits, specifying its coordinates on this cube: one island is (0, 0, 0), it has three bridges to the islands (1, 0, 0), (0, 1, 0), and (0, 0, 1), each of which has two further bridges out of it corresponding to flipping further bits, and so on.

At each end of each bridge, there is an islander assigned to guard over that particular bridge. [For what it’s worth, the islanders speak an odd language in which the term for “guards over a bridge on the side of it corresponding to the bit 1” is “has blue eyes” and the term for “guards over a bridge on the side of it corresponding to the bit 0” is “has non-blue eyes”]

There is a certain ritual according as to which bridges are sometimes destroyed and their guards commit suicide (or, as the islanders euphemistically refer to it, “go on a ferry ride”). Specifically, every morning, the two guards of each bridge look out at the other guards on their own island and report what they see. If they report the same pattern of live and dead guards to each other, all is well; otherwise, if they report differing patterns, they destroy their bridge and commit suicide that midnight.

The islands all exist in perfect harmony, with no bridge destructions, for many years.

But one day, The Guru comes to town, takes a look at island (0, 0, 0), and decides he doesn’t care for it. He destroys the island and all the bridges out of it; that night, all the guards to those bridges commit suicide, no longer having a bridge to watch over.

What happens from that point on? In particular, what happens to island (1, 1, 1)?

Well, go ahead and work it out on paper if you like. It’s easy enough. You don’t have to worry about who knows what when; there’s nothing about knowledge here. There’s just the mechanical bridge-suicide rules, as given above. See where they take you.

28

Because the brown-eyed person sees 100 people with blue eyes, not 99 people with blue eyes.

29

You’re right, thanks.

30

The guru only says it once, not once per day.

The guru’s statement’s only function is to catalyze the mathematical induction that one uses to logic their way out of it. Without the guru’s statement, the 1 Blue Eyes/100 Brown Eyes version of the problem cannot be solved, and that version of the problem bootstraps the solution for N Blue-Eyed People.

31

Assume there are 100 people with blue eyes and 100 with not-blue eyes. Blue eyed people know there are either 99 or 100 blue eyed people. Non-blue eyed people know there are either 100 or 101 blue eyed people.

Literally everyone knows that nobody can leave the island on the first, second, or third day. Indeed nobody can possibly leave the island until day 99 at minimum. So why does the problem require the islanders to wait 99 days, when literally no information is gained between day 1 and day 98?

32

Except that it seems to me in what we might call Case D with 4 people (and subsequent cases with even more people), Case B can no longer be applied and used as a basis for action in Case C, and therefore Case C could not be used in D.

In other words, with four people, when the guru speaks, each blue-eyed person can see three blue-eyed people. Each will think “If I don’t have blue eyes, those three will follow the process in case C --if they DON’T leave on day three, I must also have blue eyes. We can all leave on day 4.”

But this seems faulty, because the decision to not leave on day three would have been based on case C, which in turn would be based on B, but B does not apply because everyone can see that all of the others can also see multiple blue-eyed people and therefore could not make an inference about what any individual’s failure to leave on the first night might mean.

33

Information is gained from other blue-eyed people not leaving.

34

Another way to approach the difficulty I have with this is, why is the following a given (as it seems to be in some of the explanations):

“n people with blue eyes will leave on day n”

I can see how this works for n = 1, 2 or 3, but not why it is true for the general case. Solutions based on this seem to be assuming something that has not been proven.

35

What is the quantified piece of information that the Guru provides that each person did not already have?

I don’t know the answer to this. The Guru only verbalized something that everyone already knew since they are all perfect logicians.

36

Yes, I think that’s the real problem: 100 people follow exactly the same steps of logical deduction, and know that the other 99 people are thinking exactly the same way, all the time not communicating with each other. It assumes logical deduction that’s just too perfect.

37

What information, though? That there are at least n blue-eyed people? But they already know that – they can see them.

38

Information about who knows that who knows that who knows that who knows that… who knows that there at least n blue-eyed people.

You might say “Well, everyone knows that everyone knows that everyone knows that… everyone knows that there are at least n-blued eye people, from the start!”.

You would be wrong.

Part of the reason I gave my archipelago rephrasing is because it seems to make clear for some people what is hard for them to see in the information/knowledge based account. The things the islanders at some particular island all know are the things which are true at every island within 1 bridge of it [since every particular islander can’t tell their own eye color, so they’re not sure whether they’re on this island or the one across their bridge]. The things everyone at an island knows that everyone knows are the things which are true at every island within 2 bridges of it. The things everyone at an island knows that everyone knows that everyone knows are the things which are true within 3 bridges of it. Etc. [And, of course, the use of a 3-dimensional cube, with 3 bits to each island, is arbitrary; it might as well be 100]

39

Okay, here’s what is confusing me: I can read and mull over why the explanation above is right.

What I don’t understand is why the common-sense version (the guru’s statement is useless because everyone already knows there’s at least one blue-eyed person) is wrong. What am I missing that I don’t get the difference between the guru saying “There is at least one person with blue eyes” and being able to see that there’s at least one person with blue eyes? Why does speaking the sentence out loud make a difference?

40

If I’m one of the blue eyed guys, when the guru speaks, I now know something about what all the other blue eyed guys know.

Think about the case where there are just two blue eyed guys. Before the guru speaks, all I know is that there is at least one guy with blue eyes. I don’t know that the other blue eyed guy knows that. But after the guru speaks, I do know the other blue eyed guy knows it. So my information has changed.

Maybe “my information has changed” isn’t exactly the right thing to say–I haven’t learned anything about how things were before the guru spoke. Rahter, the guru’s speaking has changed the way things are now.