My write-up of the "Blue Eyes" solution (SPOILER A

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

steveshafer@gmail.com
Posts: 3
Joined: Fri Apr 17, 2015 8:38 pm UTC

Blue Eyes: intrinsic contradiction?

Postby steveshafer@gmail.com » Fri Apr 17, 2015 10:03 pm UTC

I arrived at the solution offered by Randall: on day 100 the blue eyed people leave. However, I also concluded that the Guru was not communicating any information, as mentioned by others on this post. These seemed irreconcilable.

I believe that there is a solution in which a Guru is not required. If so, then both statements are correct: on day 100 the blue eyed people leave, as explained by Randall, but there is an alternative solution. In the alternative solution, everyone figures out his or her eye color before the Guru arrives. If my logic is correct, that explains the apparent contradiction that the Guru is not communicating any information. The "contradiction" is in the formulation of the problem itself. It says that the islanders are perfect logicians. They can't be if they missed a solution to the problem that did not require the Guru!

First, here is a simple explanation of Randall's solution:
What if there were only 1 pair of blue eyes? In that case, the person with the blue eyes would look around, see zero blue eyes, and leave the island on Day 1.
What if there were only 2 pair of blue eyes? Each person with blue eyes would see only one person with a pair of blue eyes. If that were the only pair of blue eyes, that person would leave on the first night. Since that person doesn’t leave on the first night, both would leave on the second night.
What if there were only 3 pairs of blue eyes? The person with the third pair of blue eyes would see that the first two people didn’t leave on the second night. All three would leave on the third night.
What if there were only 4 pairs of blue eyes? The person with the fourth pair of blue eyes would see that the other three people with blue eyes hadn’t left on the third day. He would join them and depart on the fourth day.

By extending this logic, on the 100th night all 100 people with blue eyes depart the island.
More generally, if you look around on clock day X and you only count X-1 pairs of blue eyes, then your eyes must be blue too. Head for the boat!

Everyone else stays, because there is no such logic to start their departure.

OK, that is pretty straightforward. However, since it was clear to everyone that the Guru saw both blue eyes and brown eyes, how does it communicate any information when the Guru says "I see blue eyes"? If there is a solution that doesn't require the Guru, then it would follow that the Guru doesn't communicate anything. My logic may be flawed, but I'll put it forward (and risk blog wrath if I screw it up - be gentle!):

Restatement of principles:
1. Everyone is a perfect logician. This is necessary, because everyone must arrive at exactly the same solution for this to work. This is a necessary condition of the solution above. In general this is necessary for a solution to this kind of problem. As will be seen, it is necessary for this solution as well. Unstated in the formulation, but also necessary, is that everyone must KNOW that everyone is a perfect logician. This is necessary for Randall's solution, as well as my solution below.
2. I will add an assumption that everyone shows up on the island on the same day. This makes it easier to explain. However, this works if they show up at random times by resetting the clock (see below) every time someone new shows up. So this assumption simplifies the explanation. I think it is reasonably clear that by resetting the clock when the more islanders arrive the solution still works.
3. The ship is at a dock. They can't speak, but at the dock they can see the other islanders who have shown up at the dock before boarding the ship. Is this permitted by the rules? I think so. It only involves looking at the people before they board the ship. They don't need to talk, make signs, ask silly questions, or anything else. They just show up at the dock, ready to board the ship, and look around before boarding. To me that seems entirely OK by the rules.
4. To simplify the text, I will assume that the islanders are all women. This permits a using "she" rather than "he or she", "her" rather than "him or her", and also describes an island I would like to visit.

Logic:
1. Wanting to get off the island, and knowing that everyone else wants to get off the island too, each islander thinks ahead to the fact that the Guru will tell her an eye color. She will work through the logic of how she will process that information. That is explained above. She comes up with the answer above. If the Guru says "I see blue eyes" on Clock Day 1, and she see X-1 blue-eyed people on the island on Clock Day X, then she will know that she must have blue eyes also. On Clock day X, all X people with blue eyes will leave.

2. Having thought through this, she asks herself: why wait for the Guru? Let’s start the clock today! She knows she is a perfect logician. She knows she is surrounded by logical clones other than eye color. She knows they are thinking the same thing. If she can develop a simple strategy, she knows they will all develop the exact same strategy.

3. She starts a clock right now, on arrival on the island, for every eye color she sees. So do all of the other islanders, because they are all perfect logicians.

5. She follows very simple rules
a. Let X be the clock day.
b. On each day X, for each eye color, if you see X-1 people, then you have that eye color. If so, you join everyone else and leave. (this matches the solution given by Randall after the Guru says "I see blue eyes.")
c. If everyone minus 1 shows up on the dock on day 2, then someone has a unique eye color. That someone is the person who didn't show up. If everyone shows up on day 2, then at least two people have unique eye color. She says to herself: "OK, there are islanders with unique eye color." She continues the game. Maybe it will work (see below). However, in the worst case, she will wind up waiting for the Guru, as before. Nothing us lost by trying. Therefore, it is illogical not to try. It beats walking around sipping Pina Colada's and counting eye colors while waiting for the Guru to make an appearance. That could take thousands of years!

6. In the case given by Randall, nobody has unique eye colors. Therefore, nobody shows up on the dock on day 2. She concludes, correctly, that there are no unique eye colors.

7. Every day she looks at the eye colors, and determines if she sees X-1 colors. If so, she goes to the dock.

8. Her eye color is the one for which she sees X-1 colors. There will only be one such color, and it will match her color.
a. Consider the original puzzle:
1. With 100 brown eyes, and 100 blue eyes, each woman will see 99 of one color on the 100th day. Women with brown eyes will see 99 pairs of brown eyes, and will know their eyes must be brown also. Women with blue eyes will see 99 pairs of blue eyes, and by the rule will know that their eyes are blue also. So, on the 100th day, everyone will know. They all leave.
2. Let's say that 101 women have brown eyes, and 99 have blue eyes. Then on day 99, the 99 women will see 98 pairs of blue eyes. By the rule, they learn that they must have blue eyes as well, so they all leave. If they want to play by the rules, the women with brown eyes will wait until day 101. At that time, each will see 100 pairs of brown eyes, and will leave.
i. They will actually be gone on day 100. The reason is that they have correctly inferred that there are no unique eyes from the results of Clock Day 2. If you know that there are no unique eye colors, and all you see is brown eyes, then you eyes must be brown too. No reason to wait to day 101 if your hope is to get off the island!

9. The Guru shows up, and discovers she is on the island by herself. She never learns her eye color.

If these are perfect logicians, and infinitely quick thinkers, then this should occur to all of them they moment they arrive on the Island. It would be illogical to wait for the Guru if you don't have to. Is there anything wrong with this logic? Is it inconsistent with the formulation of the puzzle?

Now, what about the failure case, where there are unique eye colors? How badly does it break down?

I don't think it breaks down at all. It just gets a little more complicated. However, I still think that everyone with a non-unique eye color can leave the island before the Guru arrives. Of course, if your eye color is unique, then the only one who can communicate that to you is the Guru. So, you are stuck! However, let's explore this in some detail.

Once the clock has gone around once, and everybody who could leave by the rules described has left, there may be some stragglers because of the day 2 problem caused by unique eye colors. Still wanting to leave the island, the remaining islanders tacitly (e.g., based on logic) restart the clock. There is no reason to wait for the Guru if you don't have to. That is just not logical!

As before, everyone shows up on clock day 2. However, things are a little different. We can determine this from considering different scenarios.

1. There is only one person. Actually, this person has already figured out that her eye color is unique, because she is the only person to NOT go to the docks on the prior day 2. Why bother showing up? She has to wait for the Guru. She will eventually leave the island.

2. There are only 2 people. Day 2 only fails if there are uniquely colored eyes. When everyone else left, they have already figured out that they must have uniquely colored eyes. Otherwise, day 2 would not have failed. They have to wait for the Guru. Only 1 will leave the island.

3. There are three people: blue blue green.
a. Green sees the two blue eyes. Therefore, green realizes she is unique. She will have to wait for the Guru. Knowing she is unique, she no longer bothers going to the dock. Why should she? She knows she won't leave, and she realizes that by not going to the dock, she will help the other two. Under any circumstances, she can’t leave until the Guru reveals her eye color.
b. The clock resets.
c. On the next round, only the two women with blue eyes show up on day 2. Realizing that green has figured out that she is unique, the two blue realize they match. They board the boat.
d. The Guru shows up eventually. Only green remains. The Guru reveals her eye color, and she leaves.

4. There are three people: blue brown green.
a. On day 2, they all show up. Looking around, they see no matching pair of eyes. Not knowing their eye color, they do not get on the boat.
b. The clock resets.
c. On the next round, on day 2, they all show up again. Since they have all shown up again, they realize that none of them were able to make a determination that he or she was unique. Therefore, they must all be unique.
d. They give up, and wait for the Guru. Only 1 will leave.

5. There are four people: blue blue blue green
a. This can’t happen. Blue would have left in the very first cycle of the clock on the third round. I mention this because it is important for the following scenarios.

6. There are four people: blue blue green brown
a. On the next round all four show up on day 2. Green already knows that she isn’t blue, because if she were blue she would have left on the third round according to the rules above. However, blue also knows that she is not brown, because if she were brown then neither she nor brown would be unique. With no unique eye colors, everyone would be off the island. Therefore, she realizes that she must be unique.
b. By the same logic, brown reaches the same conclusion.
c. Since they have no chance of leaving, they decide to not return to the dock.
d. The clock resets.
e. Only the two women with blue eyes show up at the dock. Since brown and green are both gone, they realize that brown and green have figured out that they are unique. They board the boat, knowing that their eyes match.
f. Only brown or green will leave the island, once the Guru speaks.

7. There are four people: blue green brown red
a. They all show up on round 2, and can’t determine if they are unique or not.
b. The clock resets
c. They all show up again on round two, and realize that they must all be unique. They give up, and wait for the Guru. Only 1 will ever leave the island.

8. There are five people: blue blue green green red
a. They all show up on day 2. Blue and green are not certain if they are unique or not. Red looks around, and immediately realizes that she is the unique eye color. There is no point in her returning to the dock.
b. The clock resets
c. On day 2, blue and green show up. Red is missing. For red to have figured out that she was unique, the others cannot be unique. Therefore, they are matched. The eye color is determined by the usual rule: it is the color that you see X-1 times (X being the clock day).

9. There are five people: blue blue green brown red
a. The all show up on day 2. Green already knows she is not blue, because otherwise she would have left the island on day 3. She could be brown, and she could be red. She can’t tell in this round. However, if she is brown, then red will see two blue and two brown, and realize that she is unique. Similarly, if she is red, then brown will see two blue and two red, and know that she is unique.
b. The clock resets
c. They all show up again on day 2. Green knows that she is unique, because red and brown have both shown up as well. By the same logic, so do brown and red.
d. The clock resets
e. On day 2, green, brown, and red do not show up on the dock. They know that only the Guru can reveal their eye color. Only blue shows up. Realizing that they are the only ones, they realize they have matching eyes, and board the boat.

10. There are five people: blue green brown red gray
a. They all show up on round 2. They can’t figure out if they are unique or not.
b. The clock resets.
c. They all show up again. However, they realize that there is a setting whereby a conclusion needs to be drawn on keeping the clock running. So they give it one more chance.
d. The clock resets.
e. They all show up again. They have exhausted the ways that someone could figure out if she was unique, so they must all be unique. They wait for the Guru. Only 1 will leave the island.

11. There are 6 people: blue blue green green brown red
a. The all show up on round 2. Brown sees the two blue, and the two green, and realizes she is neither. She also sees the red, and knows that if she matched red there would be no unique colors. Brown knows she is unique, and stops going to the dock.
b. By the same logic red knows she is unique, and stops going to the dock.
c. The clock resets.
d. On round 2, blue blue green green show upon the dock. Since brown and red haven’t shown up, they realize that they match, and figure out their eye color based on the X-1 rule.

12. There are six people: blue blue green brown red grey
a. They all show up. Blue sees 5 colors, and can’t tell if she matches any of them. However, green sees four colors. She already knows she is not blue, or she would be off the island. She knows that if she matches brown, red, or grey, then the other two will figure out if they are unique, since that is example 11. Brown, red, and grey make the same conclusion.
b. The clock resets
c. They all show up. As a result, brown, red, green, and grey figure out they are unique. There is no point in returning to the dock. They have to wait for the Guru.
d. The clock resets.
e. Only blue shows up. They realize they must match, and leave the island.

13. There are seven people: blue blue green green brown brown grey. (I know this is getting tedious. Sorry! It helped my thinking through it to push through 7. After that the pattern is clear)
a. On day 2, they all show up.
b. Grey figures out that she must be the unique color.
c. The clock resets
d. On day 2, grey is missing. Since that means that she figured out that she is unique, the others know their eye color based on the color represented in just one other person. They all leave.

14. There are seven people: blue blue green green brown red grey
a. On day 2, they all show up. Brown knows she might be red or grey. Red and Grey reach the same conclusion, mutatis mutandis.
b. The each realize that if they match another color, then the only unique color will figure it out on this round (e.g., scenario 13).
c. The clock resets.
d. They all show up. Since brown, red, and grey all showed up again, they were unable to reach a conclusion, so they must be unique. So they decide to not return to the dock.
e. The clock resets.
f. Only blue and green show up. They realize they match. They determine their eye color by the X-1 rule, and get on the boat.

15. There are seven people: blue blue green brown red grey orange
a. On day 2 they all show up. Green knows she isn’t blue. Green thinks “maybe I match brown.” That is scenario 14. It’s solvable. Red, brown, grey, and orange reach the similar conclusions, mutatis mutandis.
b. The clock resets.
c. They all show up. Of course, that was expected. Green thinks: “Ok, if I match brown, then red, grey, and orange will now figure out that they are unique, just like in scenario 14” The others reach the same conclusion.
d. The clock resets.
e. They all show up on day 2. Green thinks: Ok, that disproves that I match brown, since Red and Grey weren’t able to figure out that they were unique. In fact, it proves that I don’t match any of the other colors, so I must be unique.
f. Brown, red, grey, and orange reach the same conclusion.
g. The clock resets
h. Only blue shows up. Knowing what that means, they get on the boat.

Regardless of the number of unique eye colors, I think that this logic will get everyone with a matching eye color off the island. Depending on whether the number that shows up is even or odd, the presence of 2 or 1 individuals allows them to immediately determine they are unique. They stop showing up, and everyone else knows they are a match. Their actual color matches the X-1 rule. If there are more than 2 or 1 individuals, then you have to cycle through a couple of times, permitting greater numbers of individuals to determine that they are not unique. In example 15, the clock resets 3 times IN ADDITION to the reset after the first count to 100 (or whatever). However, by adding enough resets, it is possible to construct examples like example 15 that gradually tick through all of the possibilities. By the last step, those with unique eyes have left the group. If nobody leaves after enough resets, then they all have unique eye colors.

Clearly, and the only one permitted to speak, only the Guru can tell someone with a unique eye color what that color is.

Thus, it seems to me illogical that they wait around for the Guru if they can figure this out without her help. If my logic is correct, then everyone with a matching eye color can get off the island before the Guru ever shows up. As a result:
1. The Guru truly isn't communicating any information when she says "I see blue eyes."
2. The formulation that they are all perfect logicians is not accurate. Perfect logicians wouldn't be waiting around for the Guru. That is the intrinsic contradiction mentioned in the subject posting.

I'd welcome knowing if I am missing something in this logic.

If you want to reply to me directly, I'm Steve Shafer: steven.shafer@stanford.edu.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11073
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Yakk » Sat Apr 18, 2015 3:19 pm UTC

You need to more clearly communicate the algorithm **each person** follows.

On its face, it looks like a case of recursion with a broken base case, but because it is not described clearly I cannot be certain.

Your argument that you could get off the island depended on there being no uniquely colored eyes. Your argument that the uniques coukd get off the island relied on the fact that non-uniquely colored eyes could get off the island.

Your logic must be flawed, because you claim two blue eyed people can exit the island without the guru. There is no way for either to distinguish it from one brown one blue.

Please describe your algorithm *that one person follows* very clearly. Do not mix in justification why it works, do that separately. Do not mix in how you thought it up, do that separately. Both of those things are useful, but a vaguely described algorithm is not convincing, nor an algorithm.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26022
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby gmalivuk » Sat Apr 18, 2015 3:32 pm UTC

In addition to Yakk's point, I don't think the ship at the dock thing is really permitted by the spirit of the rules. In the original setup, the only information you have about other people's knowledge is whether they've left ot not. I've always taken it to mean they leave secretly in the middle of the night. Allowing them to share additional information means, even if your algorithm turns out to work, it isn't a proper solution to the initial setup.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Sat Apr 18, 2015 7:50 pm UTC

I would agree with gmal, in that your "go to the dock" is an illegal communication - the islanders don't go to the dock already knowing their eye color, they go because they want to discover it (and depending on the circumstance, they may not). In the case of having a single islander with red eyes, why would all the blue and brown eyed islanders go to the docks on day 2? They don't know their eye color, they're just fishing to see if the red eyed person stays home or shows up? This goes against the spirit of the puzzle and arguably the letter too. I would take it a step further - how would an islander logically deduce the dock as a meeting place, rather than the town square or the tallest tree or Grand Central Station?

I think you have constructed an algorithm that will allow non-uniquely-colored islanders eventually determine their eye color, but there is no logical basis for adopting it over any other such algorithm. As a further complication, your algorithm isn't even optimal - by your own plans, nobody can possibly leave day 1 so why not just do everything you would do on day 2 a day sooner? How about immediately on looking over the island, go to the docks if you see anyone with a unique eye color and stay away if you don't? I would counter that by asking why they should do that over any other course of action, and then reminding you that this plan only works if everybody follows it.

steveshafer@gmail.com
Posts: 3
Joined: Fri Apr 17, 2015 8:38 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby steveshafer@gmail.com » Sun Apr 19, 2015 12:43 am UTC

In reply to Yakk:

I appreciate your comments. To address your comments I will put them in quotes:

"Your argument that you could get off the island depended on there being no uniquely colored eyes."

That is not correct. The algorithm allows you to get off the island if there are uniquely colored eyes. Uniquely colored eyes only affects what happens on day 2, and would only impede someone if there were exactly two matching eyes that would otherwise exit on day 2.

"Your argument that the uniques coukd get off the island relied on the fact that non-uniquely colored eyes could get off the island."

That is not correct. Those with unique eye colors can only get off the island if the Guru tells them their eye color. There is no other source of information for them.

"blue eyed people can exit the island without the guru. There is no way for either to distinguish it from one brown one blue."

Of course their is. Randall's (XKCD's) solution relies on this as well. On day X, if you look around and you see X-1 pairs of a certain eye color, then that is your eye color as well. Just as in the original solution, you learn your information from the information provided by the others.

Let's say that there are just 6 people: three blue, and three brown, and your eyes are blue. On day 3 you see three pairs of brown eyes, and two pairs of blue eyes. Since you see two pairs of blue eyes, you leave, knowing yours must be blue as well. On the ship you are delighted to find that everyone boarded.

I apologize that the algorithm isn't clear. It's ridiculously simple, as explained in 5b:

On each day X, for each eye color, if you see X-1 people, then you have that eye color. If so, you join everyone else and leave. (this matches the solution given by Randall after the Guru says "I see blue eyes.").

In reply to gmalivuk:
I appreciate your comments.

I agree that it is not clear whether assessing who shows up at the dock is in the spirit of the puzzle. Yes, it is a form of communication. XKCD made it very clear what that people couldn't talk, sign, etc. However, there is nothing in the rules explicitly requires the only communication be standing in one place and looking at each other. After all, they have been on the island for years! Here is the actual text from the puzzle:

"Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate."

So, if you can see everyone else AT ALL TIMES (emphasis added), then it follows that you can see who is leaving the group. That seems close enough to "the dock." However, I don't disagree with you about the dock. I considered it not obviously allowed nor disallowed.

However please note that the dock is only required for the day 2 problem, and that only occurs if there are islanders with unique eye colors. For the problem as posted, with 100 individual of each eye color, the dock is not necessary. They will know their eye color on the designated day just by looking at each other.

Of course, they won't know that there is no day 2 problem. However, if we eliminate the dock entirely, and just let the algorithm fail if anyone has a unique eye color, it will still work in this case. That, alone, is enough of a reason for the islanders to try it. It would be illogical not to try.

My interest in posting the algorithm is to get feedback on the logic, not on how one parses the semantics of the puzzle. Do you think the logic is correct?

In reply to Gwydion,
I again apologize that the logic wasn't more clearly explained. Other than on day 2 they don't go to the dock to discover they eye color. They will already know, as explained in my posting, and above.

You ask why all the blue and brown eyes go to the dock on day 2 if there is one person with red eyes. That is required by the algorithm, repeated here: "On each day X, for each eye color, if you see X-1 people, then you have that eye color." That is the same algorithm as in the correct answer given by Randall, but applied to all eye colors, not just blue. However, by the algorithm, if one person has red eyes, then everybody except for the person with red eyes sees 1 pair of red eyes. By the algorithm, they go to the dock. They don't go to the dock to go fishing (very funny! was that intentional?). They go because that is what the algorithm requires. However, if there is a unique eye color, the failure is obvious (I think).

I love your observation that the algorithm would be more logical by starting on Day 2, rather than waiting an unnecessary day. YES!! I considered presenting it that way, but decided that it made the solution harder to explain. One could also say that it is inefficient to use days as the clock unit. Maybe they should X should increment every hour. If they have watches, they could even have it incremented every minute and get off the island in two hours! And, of course, they could start at minute 2, to save a minute!

If it really is more logical to start at day 2 (and I agree that it is), then it doesn't actually change anything. They will do whatever is most logical. Correct? It doesn't change the fact that a logical solution exists without needing the Guru.

You ask why go to the dock. First, as mentioned above, the dock is only necessary for the day 2 problem. However, the dock seems like the logical destination, since that is where the ship is. Yes, it could be a town square, tallest tree, or grand central station. Since my posited island is all women, it could even be the ladies room. The dock simply seems logical. However, these are all super logical people. They will all arrive at the same answer, whether the dock or some other more logical choice. We could change the "dock" to "logical place to go to leave the island" and leave it at that. They will all arrive at the same solution. That's fundamental to the design of the puzzle.

You suggest "looking over the island, go to the docks if you see anyone with a unique eye color, and stay away if you don't". That is an accurate description of day 2.

You note that "this plan only works if everybody follows it."

Absolutely! That is an absolute condition of any solution to the puzzle. That is true for the solution in which everyone leaves on day 100 after the Guru says "I see blue eyes." Why do you point it out? Are you aware of a solution that doesn't require everyone to follow it?

I don't think we need to worry about starting on day 1 or day 2, or whether the location is the dock or the ladies room. It's silly for use to even discuss it at all. The point is that the islanders will do whatever is most logical, and they will all follow the same rules exactly. If you accept that (and you MUST, it is a condition of the puzzle), then a solution exists that will get them off the island without the Guru.

Do you agree?

Again, thank you for reviewing my suggested solution.

Steve Shafer

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Sun Apr 19, 2015 2:28 am UTC

Steve -

Interesting take, though I think you missed the point when I tried to restate your proposed strategy - if you're allowed to create a strategy that says "go here if A, go there if B", why not take it further? On day one, if you see two islanders with the same eye color, grab their hands and put them together. This will get all the islanders with non-unique eyes off the island in only as much time as it takes to sort, and since nobody can get them off without a Guru, this solution is "optimal". Why waste days counting?

You're interpreting this as "every islander wants to leave as fast as possible, how can they do it?" The puzzle is stated actually makes no mention of whether the islanders want to leave, but rather that they must leave once they can deduce their eye color with certainty. What if one of the islanders doesn't want to leave? Nothing in your algorithm forces them to visit the dock with the others. The guru's announcement, however, makes it impossible for a perfect logician with blue eyes to remain on the island any longer than X days. Your algorithm allows islanders to leave provided they all agree to use it; xkcd's solution guarantees they leave no matter what.

Also, I think this was Yakk's point - imagine two blue eyed islanders (no one else) on the island. How can either of them use your algorithm to leave? How can they ever be certain that one of them doesn't have brown eyes? Both would show up on the dock day two, but what does that mean?

And the fishing pun was a happy accident, but thanks!

User avatar
TheGrammarBolshevik
Posts: 4878
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Going to and fro in the earth, and walking up and down in it.

Re: Blue Eyes: intrinsic contradiction?

Postby TheGrammarBolshevik » Sun Apr 19, 2015 3:38 am UTC

steveshafer@gmail.com wrote:She knows she is surrounded by logical clones other than eye color. She knows they are thinking the same thing. If she can develop a simple strategy, she knows they will all develop the exact same strategy.

Are you sure she knows any of this? As I read the problem, all she knows is that she and the other islanders are perfect logicians. Following the puzzle description, I take this to mean that they believe all the logical consequences of their beliefs. However, it doesn't follow that they are alike in other respects, e.g. that they have the same thoughts, the same desires, or adopt the same strategies.
Nothing rhymes with orange,
Not even sporange.

steveshafer@gmail.com
Posts: 3
Joined: Fri Apr 17, 2015 8:38 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby steveshafer@gmail.com » Sun Apr 19, 2015 6:23 pm UTC

In reply to TheGrammarBolshevik and Gwydion:

"Are you sure she knows this?"

As a practical matter, of course not. Everyone is different. None of this works in real life.

However, this is a hypothetical logic problem, so the rules can be set arbitrarily. The rules are 1) perfect logic by all islanders (explicitly stated by Randall in the formulation of the puzzle), and 2) knowledge that everyone else is a perfect logician (implied by the statement "everyone on the island knows all the rules of this paragraph").

Two observations:

First, if the Guru had said "I see brown eyes, and I seen blue eyes" then everyone would leave on day 100 knowing her eye color. They day 1 case works properly if the Guru states both eye colors. I point this out because it logically raises the question: "why wait for the Guru to state the obvious?"

Second, and more generally, what does it actually mean to say that "everyone is a perfect logician."? It means they will all figure out the same solution, and act accordingly. This is why 100 people with blue eyes leave 100 days after the Guru says "I see blue eyes." With all respect, the solution is reasonably obvious. For the obvious solution, that's easy to accept that they all act identically. And, of course, that is necessary for the solution to work.

HOWEVER, nothing says that the principle of binding all islanders to the same solution is limited to obvious solutions. I will restate that for emphasis: Nothing says that the principle of binding all islanders to the same solution is limited to obvious solutions.

Fundamentally this is a deep and profound statement. It should not be dismissed lightly. By binding everyone to the same solution, you create the opportunity for deeper and deeper solutions to the puzzle. I proposed a solution where you don't have to wait for the Guru to speak, but start the clock on Day 1. It was pointed out that there are ways of making this "more logical", for example starting on day 2 rather than day 1. Yes, I agree completely. There may be yet more logical solutions that involve holding hands, walking sideways, or solving cube roots. If such a solution exists, the islanders will all find it, act accordingly, and leave.

However, this gets to what I believe is the deep flaw in my proposed solution. I have proposed a deeper solution to the puzzle than waiting for the Guru to speak. In suggesting that the clock start on day 2, Gwydion suggests a deeper solution. Yes! In asking why wait a full day, I've offered a deeper yet solution. Yes! The various replies to my comments propose increasingly more logical solutions. Yes!! And there, precisely, is the flaw.

The flaw in my solution is that there is no way for our perfect logicians to determine that search for the most logical solution has found it. It is impossible to rule out the possibility of a better solution. It is not logical to act on any solution if the possibility exists of a better solution. That being the case, they spend their years on the island thinking of deeper and deeper solutions. Only after the Guru speak does a single obvious solution appear.

However, can they actually know, with absolute certainty, that even the obvious solution after the Guru speaks is the best solution? This didn't occur to me when I first saw the puzzle (Friday). However, having thought through this with your help, it is an interesting twist on the obvious solution. I pointed out that my requirement for absolute binding of the islanders to a single "best" solution is also required for the obvious solution after the Guru speaks. Does not my fundamental flaw also apply to the obvious solution? After the Guru speaks, can the islander's know with absolute certainty that there is not a better solution than the solution of counting days? It doesn't matter that I can't think of a better solution. That does not prove that a better solution does not exist. Is it possible that the fundamental flaw in my approach is a fundamental flaw in ANY solution? Is it possible that the binding of the islanders to a single "best" solution forever chains them to the island, since they can't know for certain that they have found the best solution?

We know there are limits to provability (e.g., Godel's incompleteness theorem). Perhaps this demonstrates a flaw in all problems constructed on the notion of a single best logical solution.

Does this make sense?

Thanks again for helping me think through this.

Steve

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby SPACKlick » Sun Apr 19, 2015 6:35 pm UTC

The original solution doesn't rely on anybody knowing any solution, it only relies on them knowing the rules.

In general the islanders cannot know their own eye colour.
The islanders know no other islanders know their own eye colour only because they don't leave.
The fact that leaving can only occur once per day sets the rhythmn
The information the guru imparts is that "there are blue eyes" is common knowledge, no logician can posit with any positive confidence any scenario where any other islander believes there are no blue eyes (at any level of abstraction).

This is the foundation of the established solution.

Your solution requires all the islanders to decide on the same set of rules independently and there's no reason for them to do that. These rules cannot be logically deduces they are arbitrarily decided.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby douglasm » Sun Apr 19, 2015 6:44 pm UTC

steveshafer@gmail.com wrote:You note that "this plan only works if everybody follows it."

Absolutely! That is an absolute condition of any solution to the puzzle. That is true for the solution in which everyone leaves on day 100 after the Guru says "I see blue eyes." Why do you point it out? Are you aware of a solution that doesn't require everyone to follow it?

The problem is that there is nothing forcing everyone to follow it. For the official solution, every single part of the plan's derivation is 100% forced by the rules of the puzzle. Everyone can depend on everyone else following the plan because the puzzle rules force everyone to follow it. Every step of the way, it's "at this point, the rules of the puzzle dictate that people will do X". Any plan that depends on the islanders mutually deciding on a cunning scheme that does not have that kind of backing is unreliable because there is nothing to force every islander to come up with the same cunning scheme.

steveshafer@gmail.com wrote:Second, and more generally, what does it actually mean to say that "everyone is a perfect logician."? It means they will all figure out the same solution, and act accordingly.

No, it does not. A perfect logician will instantly derive all facts that are possible to prove from the facts that the logician knows. No more. no less. In particular, it does not mean that they all have identical thoughts.

steveshafer@gmail.com wrote:However, can they actually know, with absolute certainty, that even the obvious solution after the Guru speaks is the best solution?

Whether it's the "best" solution is irrelevant. The rules of the puzzle force them to follow it whether they deem it best or not.

It is trivial to prove with 100% certainty that, if there is only 1 blue-eyed person, he will leave immediately when the Guru speaks. This does not depend on evaluating the quality of a plan, it is a simple consequence of the fact that the Guru's statement would unambiguously and with certainty reveal his eye color to him.

On day 2, the islanders know that, no matter what clever plans might be in play, a lone blue-eyed person would have already left. Thus, if there were only 2 blue-eyed people they would realize their eye color at that point and leave. There is no element of planning or scheming involved in this, it's a simple logical deduction. "He's the only blue-eyed person I see, a lone blue-eyed person would have left yesterday, he didn't leave yesterday, therefore he's not the only blue-eyed person, there are no blue-eyed people other than him and me, therefore my eyes are blue." 100% combining facts to prove other facts, not implementing a plan. This behavior, the combining known facts to prove other facts, is what the definition of "perfect logician" means, and is therefore something that every islander will do.

Repeat similar logic on day 3 and later, and you get the official solution. At every step it's fact + fact = derived fact, with no dependency on planning, agreement, or plan quality assessment.
Last edited by douglasm on Sun Apr 19, 2015 6:46 pm UTC, edited 1 time in total.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Sun Apr 19, 2015 6:45 pm UTC

douglasm from like 20 pages ago wrote:To prove that it can't be done in less than 100 days, consider it from the other direction. If the blue-eyed people leave on day X, why would they do so? The possibility of 99 blue-eyed people must have been eliminated within the past 24 hours. The guru's statement obviously doesn't do that in that short amount of time, so it has to have been eliminated some other way. The only other possible way is that if there were only 99 blue-eyed people they would have left on day X-1. Now, why would 99 blue-eyed people leave on day X-1? It must be either because of the guru's statement or because 98 people would have left on day X-2. Now, why would 98 blue-eyed people leave on day X-2? And so on.

You eventually get down to a lone blue-eyed person would leave on day X-99. It's not possible for anyone to leave before day 1, so the earliest possible date for the hypothetical loner to leave is day 1 and X cannot therefore be less than 100.
That's why the islanders actually do follow the official solution rather than waiting for a better one - no better one exists given the parameters of the puzzle and forbidding additional communication or cooperation. Just wanted to add that to his already excellent reply.

User avatar
TheGrammarBolshevik
Posts: 4878
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Going to and fro in the earth, and walking up and down in it.

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby TheGrammarBolshevik » Sun Apr 19, 2015 7:08 pm UTC

douglasm wrote:
steveshafer@gmail.com wrote:Second, and more generally, what does it actually mean to say that "everyone is a perfect logician."? It means they will all figure out the same solution, and act accordingly.

No, it does not. A perfect logician will instantly derive all facts that are possible to prove from the facts that the logician knows. No more. no less. In particular, it does not mean that they all have identical thoughts.

I just want to cosign this.

The puzzle says
They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly.

I take the part after the hyphens to be a definition of what it is to be a perfect logician. A perfect logician is someone who immediately deduces all the logical consequences of what she knows. No more, and no less, as douglasm says.
Nothing rhymes with orange,
Not even sporange.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11073
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Yakk » Sun Apr 19, 2015 9:00 pm UTC

steveshafer@gmail.com wrote:On each day X, for each eye color, if you see X-1 people, then you have that eye color. If so, you join everyone else and leave. (this matches the solution given by Randall after the Guru says "I see blue eyes.").


Two people on the island. Both see the other person has some color of eye.

By your algorithm, they go to the dock on day 2 and leave.

Your algorithm failed. One had brown eyes, one had blue. They both saw 1 person with some color of eye, and so by your algorithm where supposed to leave the island on day X=2.

The rest of your post is dross **if** you actually described your algorithm. If you failed to describe your algorithm, then actually describe your algorithm in brief without justification or motivation mixed in. It should be the algorithm that an individual follows given what they see, not "what should happen in this situation".

And no, I won't inject extra stuff into your algorithm based off your motivations or other parts of your post. The entire point of asking for a simple algorithm is to not have to wade through the rest of your justifications, arguments and motivations to determine what you are trying to say. The rest of the post -- the motivations, arguments, justifications -- can be background, but the absolute minimum for a coherent "there is a better way" argument is producing an algorithm that actually works.

I want a simple, clear and concise algorithm that is self contained. No "but somewhere else I covered that case" excuses. No arguments (within the algorithm description) for why it works, or motivational descriptions, or whatever. That can go elsewhere. And as we are talking about the behavior of individuals on the island, the algorithm should work based on the information that the islander knows. The algorithm must be the same for every "possible island" that the islander could be on (where they see 0 to N-1 people of a particular eye color, where N is the number of people on the island). You can even give me a simplified algorithm where the islander knows that everyone has either blue or brown eyes. The algorithm can *branch* (ie, have an if clause) based off of how many (say blue) eyed people the islander sees -- if they see 0, they can behave differently than if they see 1 or 3 or 27 -- but the one algorithm description should include all possible branches.
Last edited by Yakk on Tue Apr 21, 2015 5:18 am UTC, edited 2 times in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Sun Apr 19, 2015 11:36 pm UTC

Yakk wrote:"On each day X, for each eye color, if you see X-1 people, then you have that eye color. If so, you join everyone else and leave. (this matches the solution given by Randall after the Guru says "I see blue eyes.")."

Two people on the island. Both see the other person has some color of eye.

By your algorithm, they go to the dock on day 2 and leave.

Your algorithm failed. One had brown eyes, one had blue. They both saw 1 person with some color of eye, and so by your algorithm where supposed to leave the island on day X=2.

The rest of your post is dross **if** you actually described your algorithm. If you failed to describe your algorithm, then actually describe your algorithm in brief without justification or motivation mixed in. It should be the algorithm that an individual follows given what they see, not "what should happen in this situation".


Agreed.

There is a problem with the algorithm on day 2 when there are unique eye-colours among the population. Saying that the algorithm works when there are 6 islanders: 3 blue; 3 brown doesn't resolve the problem of what happens on day 2 when there are unique eye-colours.

The algorithm works for X>2 provided it works as advertised for X=2 (pairs of matching eye-colours leave; no other combinations do, and this happens without communication - including pretending you're about to leave the island when you don't already know your eye-colour with certainty)

The Ox Man Cometh
Posts: 1
Joined: Tue Apr 21, 2015 6:59 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby The Ox Man Cometh » Tue Apr 21, 2015 7:02 pm UTC

With sufficient blue eyed people, there will be a "floor" for the real minimum of people anyone can see with blue eyes.

Let's say there are 100 blue 100 brown. I have blue eyes. That means I see 99 blue eyed people.

This tells me a few important things. I know there are blue eyed people, I know that everyone must know there are blue eyed people, and I know the minimum number of blue eyed people anyone can see is 98.

So let's say I assume I don't have blue eyes. That means anyone with blue eyes will see 98 blue eyed people, and know that there are blue eyed people, that everyone else knows that there are blue eyed people, and that the minimum number of blue eyed people anyone can THINK THERE ARE is 97.

This is the key: I, a blue eyed person, am now reasoning as another blue eyed person, and finding the floor because of it. The floor is 97, because they could see one less than me, if I'm not blue eyed, and could assume they don't have blue eyes. But no one will ever see less than 98 people with blue eyes, because I see 99, and they can only exclude themselves.

That means the minimum number of people there can be with blue eyes is n-1, and the minimum anyone could think there were is n-2, where n=the number of blue eyed people the reasoner is seeing. As long as n-2 > 3, you can know that blue eyed people are common knowledge, and that everyone else can too.

Then, you just leave on day n+1, provided all the blue eyed people haven't already left. They may leave one day before, at which point you'd know your eyes aren't blue.

Then you can do the same for every other color (you'd start with the lowest number you can see) and as long as everyone else doesn't leave before you, you can figure out your eye color.

That's probably intolerably sloppily worded, but I hope you all get what I'm saying.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Wildcard » Wed Apr 22, 2015 5:36 am UTC

steveshafer@gmail.com wrote:I apologize that the algorithm isn't clear. It's ridiculously simple, as explained in 5b:

On each day X, for each eye color, if you see X-1 people, then you have that eye color. If so, you join everyone else and leave. (this matches the solution given by Randall after the Guru says "I see blue eyes.").

Actually this fails on day 1 because your "for each eye color" is ill-defined. Is this "for each eye color THAT YOU SEE" or is it "for each eye color THAT YOU MIGHT POSSIBLY HYPOTHETICALLY HAVE"?

If you assume that SOMEONE else has the same eye color as you do, and if that assumption is correct, then your algorithm works just fine, IF that assumption is always true. In other words, your algorithm only works if (a) it is impossible for there to be only one person with a given eye color, and (b) that fact is common knowledge.

Otherwise we get the following scenarios, in two forms, based on how you define "for each eye color":

Case 1: If you define "for each eye color" as "for each eye color that is visible to you", then the algorithm fails given an island with 1 blue-eyed and 1 brown-eyed person. (Work it out. What do they do, following your specified algorithm that I quoted above?) (Hint: Yakk already answered this.)

Not only that, but the algorithm fails spectacularly if you have exactly three people, one with blue eyes, one with green eyes and one with brown eyes. What does your algorithm do THEN, huh? :) (Hint: It's indeterminate. But spectacularly so!)

Case 2: If you define "for each eye color" as "for each eye color that you MAY POSSIBLY HAVE", then day 1 you see X-1 = 0 people with purple eyes, so you follow the algorithm by deciding your eyes must be purple. But wait—also according to the algorithm, your eyes must be pink! How confusing. Anyways, everyone would have to leave on day one because they all see X-1 = 0 people with SOME eye color, whether pink, purple, vomit green, or "gosh, that's BLUE".

Regardless of the definition you provide for the "for each eye color" step, the algorithm doesn't work—for ANYONE—unless it is common knowledge that there are no unique eye colors on the island. Do you understand?

(Guess what? That common knowledge, about the non-uniqueness of the eye color blue, IS the precise information that the Guru provides in the original puzzle! But understanding this fully depends on a THOROUGH grasp of the meaning of "common knowledge.") (More precisely, the Guru provides the common knowledge that there are not ZERO people with eye color blue. One day later it is common knowledge that blue is not a unique eye color, i.e., there are at least two people with blue eyes.)

(Also, @steveshafer: Please don't bother replying to the above paragraph with the usual rebuttal that "but everyone already knows there aren't zero people with blue eyes, so the information you say the Guru provides isn't new to anyone!" It's been done on every *single* page of this 34 page, NINE YEAR discussion. Just carefully clear up the meaning of "common knowledge." It isn't common knowledge that there is at least one person with blue eyes until the Guru speaks, because "everybody knows that everybody knows that there is at least one person with blue eyes" is NOT what common knowledge means.)

On another note, the following quote...what, four pages back?...got zero attention and I think it deserves some. It is an alternate approach to explaining the solution which is much easier to grasp intuitively, AND it happens to be exactly correct:
GrandOpener wrote:There are two things that made it harder for me to understand the explanation that I think could be stated more clearly. (Or perhaps just more in line with my own thinking patterns.) Regardless, I'll leave them here with the hope that my contributions add something to the conversation.

The "everyone knows [repeat]" phrasing is correct, but mind bending. Stating that people are interchangeable, and thus I only need an individual chain of I know person X knows that person Y knows..., rather than a full web of everyone, everyone, everyone, makes it much easier to think about. (And then whatever conclusion about that single chain can be made about every possible chain, since people are interchangeable.)

Secondly, thinking about the problem in terms of common knowledge is very difficult. It's like reasoning what happens after the guru speaks coming from the direction of the situation with 100 rather than the situation with 1. Instead, it was much more useful for me to think about the "contagion of uncertainty" than about the knowledge. Specifically, when I consider what people know, I cannot be certain about my eye color. When I consider what I know person X knows, I cannot consider my eye color since I don't know what it is, and I cannot consider his color, since he doesn't know what it is. This creates a very straight-forward iterative chain, very similar in concept to starting with what would happen on the island after the guru speaks if only one islander had blue eyes. Once you understand the "contagion of uncertainty," it's fairly straightforward to see that there will be uncertainty about everyone's eye color when considering what is common knowledge among all islanders.

Thanks again for the lively discussion.

This idea of the "contagion of uncertainty" is, IMO, brilliantly phrased. I'll put it in my own words:

When I think about any eye colors at all, I of course don't know my own eye color, so I can't come to any conclusions that would depend on knowing my eye color.

When I think about what Pete knows, I know he doesn't know his eye color, and I don't know my eye color, so in considering Pete's ideas about things I have two uncertainties.

When I think about what Pete knows about what John knows, there are three uncertainties. And so forth.

Actually GrandOpener's wording may have been better than mine anyway. But regardless, this is a way of looking at it from the other direction.
There's no such thing as a funny sig.

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Wed Apr 22, 2015 11:43 am UTC

The Ox Man Cometh wrote:With sufficient blue eyed people, there will be a "floor" for the real minimum of people anyone can see with blue eyes.

Let's say there are 100 blue 100 brown. I have blue eyes. That means I see 99 blue eyed people.

This tells me a few important things. I know there are blue eyed people, I know that everyone must know there are blue eyed people, and I know the minimum number of blue eyed people anyone can see is 98.

So let's say I assume I don't have blue eyes. That means anyone with blue eyes will see 98 blue eyed people, and know that there are blue eyed people, that everyone else knows that there are blue eyed people, and that the minimum number of blue eyed people anyone can THINK THERE ARE is 97.

This is the key: I, a blue eyed person, am now reasoning as another blue eyed person, and finding the floor because of it. The floor is 97, because they could see one less than me, if I'm not blue eyed, and could assume they don't have blue eyes. But no one will ever see less than 98 people with blue eyes, because I see 99, and they can only exclude themselves.

That means the minimum number of people there can be with blue eyes is n-1, and the minimum anyone could think there were is n-2, where n=the number of blue eyed people the reasoner is seeing. As long as n-2 > 3, you can know that blue eyed people are common knowledge, and that everyone else can too.

Then, you just leave on day n+1, provided all the blue eyed people haven't already left. They may leave one day before, at which point you'd know your eyes aren't blue.

Then you can do the same for every other color (you'd start with the lowest number you can see) and as long as everyone else doesn't leave before you, you can figure out your eye color.

That's probably intolerably sloppily worded, but I hope you all get what I'm saying.


I only see 99 blue-eyed people; I know that Bob sees at least 98 blue-eyed people; I know that Bob knows that Carol sees at least 97 blue-eyed people; I know that Bob knows that Carol knows that David sees at least 96 blue-eyed people; I know that Bob knows that Carol knows that David knows that Erica sees at least 95 blue-eyed people; and so on.

The knowledge that's common to me and Bob is the colours of the other 198 people's eyes. For me, Bob, Carol, David and Erica, it's the colours of the other 195 people's eyes. For me and the 99 people I can see with blue eyes, our common knowledge is the hundred pairs of brown eyes - and for everyone on the island, there is no common knowledge about eye colours - which is why the guru's statement is needed.

The guru's statement (and it being common knowledge) means that, at the end of the ridiculously long chains of what I know Bob knows Carol knows David knows etc, rather than the minimum possible number of pairs of blue eyes dropping to 0, it stays at 1, even after the chain is long enough that there's no individual whose blue eyes are common knowledge to the entire chain.

duodecimus
Posts: 24
Joined: Tue May 19, 2015 12:25 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby duodecimus » Wed Jun 03, 2015 11:08 pm UTC

rmsgrey wrote:I only see 99 blue-eyed people; I know that Bob sees at least 98 blue-eyed people; I know that Bob knows that Carol sees at least 97 blue-eyed people; I know that Bob knows that Carol knows that David sees at least 96 blue-eyed people; I know that Bob knows that Carol knows that David knows that Erica sees at least 95 blue-eyed people; and so on.


I don't think this holds water. Nobody will ever consider a depth beyond 97.
Since I can see 99 blue eyed people, I know that no other blue eyed person will be seeing less than 98 blue eyed people.
If I am not blue eyed, those people all know they can see no less than 97 blue eyed people.
If I am blue eyed, those people all know that no other blue eyed person will see less than 98 blue eyed people.
Considering a person seeing a number lower than the number I see -2 is pointless, as that can never happen.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26022
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby gmalivuk » Wed Jun 03, 2015 11:15 pm UTC

You're missing the depth of the "know" chain, though.

Sure, I know that Erica sees at least 98 blue-eyed people, and maybe it happens that David also knows that Erica sees at least 98 blue-eyed people, but I don't know that. What I know is that Bob knows that Carol knows that David knows that Erica sees at least 95 blue-eyed people.

What the guru provides is common knowledge (i.e. the recursive depth of the "know" chain is infinite), and the importance of that only becomes apparent when you build the chain of inference explicitly.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phlip
Restorer of Worlds
Posts: 7550
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby phlip » Thu Jun 04, 2015 12:38 am UTC

I find it easier to think about if it's phrased in terms of "what questions can you answer?" rather than "what do you know?"... it helps make the nesting more explicit.

So, say there are 100 blue-eyed people on the island.

I go up to Alice, and ask "What's the smallest number of blue-eyed people there could be on the island?" Well Alice doesn't know her own eye colour, so she knows the count could be 99 or 100, so she answers "99".

I go up to Bob, and ask "If I was to ask Alice 'What's the smallest number of blue-eyed people there could be on the island?', what's the smallest answer she could give?" Bob doesn't know his own eye colour, so he knows Alice's answer to that question could be either 99 or 98, so he answers "98".

I go up to Charlie, and ask "If I was to ask Bob 'If I was to ask Alice "What's the smallest [etc]?", what's the smallest answer she could give?', what's the smallest answer he could give?"... then he'd probably have no idea what I was saying... but if I repeated the question a couple of times and made it clear how all the nesting worked so he was able to understand what I was asking for... then he doesn't know his own eye colour, so he knows Bob's answer could be 97 or 98, so he answers "97".

You can keep going in this vein forever... the questions get more convolulted at every step, but there's nothing in there that stops the pattern from continuing.

So then you nest it 100 levels deep, and ask one person "if I was to ask another person 'if I was to ask another person "etc etc etc"'", and have every single blue-eyed person on the island included in the chain... the final answer would be zero.
And, in particular, the question "if I were to ask Alice 'if I were to ask Bob "[etc] 'Are there any blue-eyed people on the island?' [etc]" what would he answer?' what would she answer?", where the nesting is deep enough to go through every blue-eyed person... the answer, before the guru's announcement, would be "I don't know". After the guru's announcement, the answer is "yes". This is the piece of information given by the guru.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

duodecimus
Posts: 24
Joined: Tue May 19, 2015 12:25 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby duodecimus » Thu Jun 04, 2015 3:46 pm UTC

gmalivuk wrote:You're missing the depth of the "know" chain, though.

Sure, I know that Erica sees at least 98 blue-eyed people, and maybe it happens that David also knows that Erica sees at least 98 blue-eyed people, but I don't know that. What I know is that Bob knows that Carol knows that David knows that Erica sees at least 95 blue-eyed people.

What the guru provides is common knowledge (i.e. the recursive depth of the "know" chain is infinite), and the importance of that only becomes apparent when you build the chain of inference explicitly.

Why is the previous person in the chain removed from the tally of blue eyed people?
I can see 99 blue people, how can Erica/David/Carol see anything less than 97?
While the theoretical chain might end at 0, any case where the total number of blue eyed people is less than 97 can be safely discarded as I can be certain there are at least 99 blue eyed people, and it is impossible for anyone to see less than 98blue eyed people. Those people that only see 98 will never consider a depth below 96, as that can never happen.


That said, would this change how many days it is before they left? I don't think it does, as, as you say, the chain of inference is what sets the 'timer'.

Its interesting. All the brown people think they should leave on day 100 or 101.
All blue eyed people will think they leave on day 99 or 100.
the first recursion thinks they will leave on 98 or 99
the second recusion thinks 97 or 98
less than this can't exist

So there are only actually 'five' days being considered, can we cut out the 96 days nobody is possibly considering?

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Thu Jun 04, 2015 4:54 pm UTC

duodecimus wrote:
gmalivuk wrote:You're missing the depth of the "know" chain, though.

Sure, I know that Erica sees at least 98 blue-eyed people, and maybe it happens that David also knows that Erica sees at least 98 blue-eyed people, but I don't know that. What I know is that Bob knows that Carol knows that David knows that Erica sees at least 95 blue-eyed people.

What the guru provides is common knowledge (i.e. the recursive depth of the "know" chain is infinite), and the importance of that only becomes apparent when you build the chain of inference explicitly.

Why is the previous person in the chain removed from the tally of blue eyed people?
I can see 99 blue people, how can Erica/David/Carol see anything less than 97?
While the theoretical chain might end at 0, any case where the total number of blue eyed people is less than 97 can be safely discarded as I can be certain there are at least 99 blue eyed people, and it is impossible for anyone to see less than 98blue eyed people. Those people that only see 98 will never consider a depth below 96, as that can never happen.


That said, would this change how many days it is before they left? I don't think it does, as, as you say, the chain of inference is what sets the 'timer'.

Its interesting. All the brown people think they should leave on day 100 or 101.
All blue eyed people will think they leave on day 99 or 100.
the first recursion thinks they will leave on 98 or 99
the second recusion thinks 97 or 98
less than this can't exist

So there are only actually 'five' days being considered, can we cut out the 96 days nobody is possibly considering?

Thing is, you, Bob, Carol, David and Erica can only see 95 pair of blue eyes that you can all see - yes, each of the five of you can see 99 pairs of blue eyes, but you can go through the process where you list all the people that Erica knows have blue eyes - that'll be Bob, Carol, David, the other 95, and maybe yourself - 98 or 99. If you think about David's list of the people Erica knows have blue eyes then they'll be the 95, Bob, Carol, maybe David himself, and maybe yourself - 97, 98 or 99. Now if you imagine Carol doing the same thing - thinking about David's list of people who Erica knows have blue eyes - she'll have the 95 and Bob, might have you on her list (you don't know), and will have herself as a maybe (she doesn't know) and will have David down as having put himself down as a maybe rather than a definite, and as having put Erica down as definitely not being on Erica's list because Erica definitely doesn't know her own eye colour - so how many is that on Carol's version of David's version of Erica's list of known blue-eyed people? 96 definites (Bob and the other 95), one that might be a definite or a definitely not (yourself), and two that Carol definitely has down as maybes (herself and David), so anything from 96 to 99. Add in Bob, and you know that his version of Carol's guess at David's prediction of Erica's list of known blue-eyed people has the 95 other blue-eyed people on, it could have you on, and that himself, Carol and David remain maybes.

It all gets a bit confusing when you try keeping the various levels of indirect knowledge straight, but the key thing is that, while you know that no-one else sees fewer than 98 blue eyeds, someone who only sees 98 blue eyeds only knows that no-one else sees fewer than 97 blue eyeds, and someone who only sees 97 blue eyeds only knows that no-one else sees fewer than 96 blue eyeds, and so on. Whatever logic you can go through having seen 99 people with blue eyes, so can the people around you but they might be starting with only 98 people they can see, so whatever number you conclude, they might be concluding one less than you.

If the recursion doesn't go all the way back to 0, then you end up getting contradictions...

Cauchy
Posts: 600
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Cauchy » Thu Jun 04, 2015 4:59 pm UTC

In saying it can be safely discarded, you're presuming knowledge that someone, somewhere doesn't have.

As a blue-eyed person on the island, I know there are more than 96 blue-eyed people, sure. Bob and Carol and David and Erica know it too, though I can't immediately figure that out without modeling them first. So I imagine Bob. The worst case scenario for Bob's blue eye count is if I have brown eyes, so I picture the possible (from my perspective) island, Island_1, which has 99 pairs of blue eyes, and I am not one of those pairs. On this island, each blue-eyed person on it sees 98 pairs of blue eyes. But I need to know how these hypothetical people are going to act, what they're considering, since this is (from my perspective) a possible world.

On this Island_1 that Bob_1 inhabits, he sees 98 pairs of blue eyes. But he wonders what Carol_1 knows. So he in turn imagines a possible (from his perspective) island, where he has brown eyes and the 98 pairs of blue eyes are the only blue eyes on the island. Here on Island_2, Carol_2 sees 97 pairs of blue eyes, and similarly constructs in her mind's eye a possible (from her perspective) island, Island_3, in which the 97 pairs of blue eyes she sees are the only blue eyes on the island. On Island_3, David_3 sees only 96 pairs of blue eyes.

But wait, you say! I know this island is not the true island, because it has Bob and Carol with brown eyes, when I know their eyes are blue! While that is the case, it doesn't mean we can throw it out. Because as far as Carol_2 knows (who is a mental construction of Bob_1, recall), this could very well be the island, so as far as she knows, this is what David_2 could really be seeing. Carol_2 knows that David_2 sees 96 pairs of blue eyes but cannot conclude a higher number. As far as Bob_1 is concerned, Carol_2 could really be Carol_1, so Bob_1 can only know that Carol_1 knows that David_1 sees 96 pairs of blue eyes. And as far as I'm concerned, Bob_1 could really be Bob, so I can only know that Bob knows that Carol knows that David sees 96 pairs of blue eyes.

In essence, I know the hypothetical island is false, but (from my perspective) Bob might considering it, so I can't throw it out. To the best of my knowledge, Bob might be considering it because he's imagining Carol imagining David. So I have to keep it in mind.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby douglasm » Thu Jun 04, 2015 7:12 pm UTC

duodecimus wrote:While the theoretical chain might end at 0, any case where the total number of blue eyed people is less than 97 can be safely discarded as I can be certain there are at least 99 blue eyed people, and it is impossible for anyone to see less than 98blue eyed people. Those people that only see 98 will never consider a depth below 96, as that can never happen.

You are constructing a hypothetical, and then resolving it by giving it information that is outside it. That doesn't work.

Alice, a blue-eyed person, looks around and thinks "there are at least 99 blue-eyed people".

Bob, a blue-eyed person, looks at Alice and considers "what might Alice be thinking?" Bob looks around and sees 98 blue-eyed people other than Alice, and concludes that Alice must believe there are at least 98 blue-eyed people.

Carol, a blue-eyed person, looks at Bob and considers "what might Bob be thinking about Alice?" Well, the Alice that Bob is imagining can't see her own eyes. The Bob that Carol is imagining can't see his own eyes. And Carol out here in reality can't see her own eyes. Carol imagines Bob looking around, and there are 97 non-Alice blue-eyed people that she knows Bob will see. Bob will actually see 98, but Carol doesn't know that because Carol is one of those 98.

David, a blue-eyed person, looks at Carol and considers "what might Carol be thinking?" Following the chain back up, David doesn't know his own eye color, so his imagined version of Carol doesn't know it either. Carol, imagined or not, doesn't know her own eye color, so her imagining of Bob doesn't know it. Bob, imagined at whatever depth of nested imagination, doesn't know his own eye color, so his imagined version of Alice doesn't know it. And, of course, Alice doesn't know her own eye color. So, the Alice imagined by the Bob imagined by the Carol imagined by David can only be certain about 96 blue-eyed people.

Erica, a blue-eyed person, looks at David and considers "what might David be thinking?" Her imaginary version of David has all the same constraints on knowledge that the real one does, but also does not know Erica's eye color because she's the one doing the imagining. This produces a chain that excludes 5 people's eye colors, resulting in a minimum blue-eyes count of 95.

This continues all the way down.

Sure, you might know that there are at least 98 people with blue eyes, but that's your knowledge. This hypothetical is talking about a combined hybrid of Alice's, Bob's, Carol's, David's, and Erica's knowledge.

duodecimus wrote:So there are only actually 'five' days being considered, can we cut out the 96 days nobody is possibly considering?

No, because there is no consensus about whether it's 95 or 96 days that need to be cut. Or is it 96 or 97? Anyway, the point is that no matter where you put your arbitrary cutoff for which days matter, the blue-eyed people and the brown-eyed people will disagree about it, and that disagreement will render it nonfunctional.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Wildcard » Thu Jun 04, 2015 8:33 pm UTC

duodecimus wrote:The same thing everyone else has said for the last 9 years in this thread before fully understanding the logic involved.
@duodecimus: Try reading this thread.

What people here are saying to you is correct. It is also confusing in the way it is explained. One of the most helpful excerpts from the thread I linked to is:
Lenoxus wrote:"I will finish this novel the day after [repeat the last three words outside this bracket three hundred times] tomorrow" really does mean something different than "I will finish this novel the day after [repeat the last three words outside this bracket two hundred ninety-nine times] tomorrow". I'm referring to two different days. It just so happens that we have a nice shorthand to say this in the English language (I can simply say "in three hundred days" or "299 days"), and we don't have such a shorthand to refer to the "everyone knows that everyone knows" situation, at least not one that non-logicians use regularly.
Can you understand how the following sentence could be true? (It's an example.)
Everyone knows that everyone knows [some fact], but not everyone knows that everyone knows that everyone knows [that fact].
Here is a way that could happen: A staff payroll list is sent to the company president, but the entire employee email list is accidentally added to the BCC line. Now everyone knows the payroll list, but they don't know that everyone else knows it. The president meets with each person privately and lets them know that the entire company received that email—but doesn't tell them he is having this meeting with everyone. Now everyone knows that everyone knows the payroll list, but they don't know that everyone else knows that everyone knows the payroll list. (I got this example years ago on this same forum; I didn't make it up. If I remembered who posted it I would give attribution.)

Does that help?

Now approach this puzzle the other way around. Answer me this question: What if there are only 5 blue eyed people on the island? On what night do they all leave?
There's no such thing as a funny sig.

duodecimus
Posts: 24
Joined: Tue May 19, 2015 12:25 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby duodecimus » Fri Jun 05, 2015 12:51 am UTC

That summary thread really ought to be in the first post.
It is very likely that I am having trouble getting into the right headspace here. I was very tempted to simply ask why each person doesn't just assume for a moment that the guide is talking about their own eye color, as I viewed the ferry as a test rather than a thing that just happens. Putting a little too much humanity in them, methinks.

I don't think I understand the logic, but I do get the paradox of:
Here may be a simpler way to put it, a point raised by many dealing with this problem: If you think the blue-eyed people can nonverbally agree on some sort of common minimum which is greater than zero, than surely the browns should agree to the same minimum, or else it's not really common to the islanders. But how? Suppose each blue thought "I see 99 blues. 99 minus 2 is 97, so 97 is the absolute common minimum to which we all agree." In that case, a brown-eyed person would go "I see 100 blues. 100 minus 2 is 98, so 98 is the absolute common minimum". If a brown instead came to conclude that the minimum is 97, that means he went one step further than a blue would. Why would he? See, this is the (initially) surprising result of the existence of a one-person difference between two people's counts of eye color, all thanks to the commonly-known fact that no one knows the color of her own eyes.


I'm basically suggesting that the blues would skip 97 days of the countdown; but the browns would follow the same logic, skip 98 days, and thus wrongly determine their eye color is blue at the same time.

Still seems dumb for a perfect logician to seriously entertain a hypothetical that is false.I feel like there should be something to that...

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby SPACKlick » Fri Jun 05, 2015 1:00 am UTC

The logician isn't entertaining a hypothetical that's false.

they're deducing that because there is information asymmetry between the logician and others may be considering a hypothetical that the logician can deduce is false. And given information asymmetry between another individual and a further individual the first individual can deduce that the second individual may be considering a hypothesis that the first individual can deduce is false and the logician can deduce is even more wrong.

So the logician isn't considering the false hypothetical, the logician is deducing that other individuals have different information and so may be considering false hypotheticals.

The extreme of these hypotheticals is that [someone may be considering that]x100 nobody has blue eyes. Everyone in the chain but the last person knows it's false but the limited information that's common to every step in the chain allows it to be being considered by the last member of the chain logically

arklarp
Posts: 3
Joined: Sun Jun 14, 2015 6:52 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby arklarp » Sun Jun 14, 2015 8:48 pm UTC

I have problems with the stated answer and the explanations so far don't seem to have resolved the issues for me. If you think I've missed any particularly good piece of explanation please let me know where it can be found so I can check to see if by some chance I have missed it or misunderstood it while reading through.

1) It seems an inescapable fact, obvious to all of us and everyone in the scenario, that none of the blue eyed people will consider leaving on the first night. This, it seems to me, instantly disproves the 'solution', because the 'solution' relies on a blue eyed person considering another blue eyed person viewing that as a possibility. The 100th person in the "A hypothesizes that B hypothesizes that C hypothesizes..." sequence still has to be someone actually in the scenario, and there is nobody who sees nobody with blue eyes. Nobody in the scenario will consider that a possibility, and so it becomes irrelevant in any deduction they could possibly make.

2) The Guru's statement does not provide any new information. The maximum amount of information that you can gain from the Guru's statement is that it ensures that everyone knows that everyone knows that the Guru sees someone with blue eyes. Since everyone can already see that everyone else can see the Guru looking at someone with blue eyes, that information is already known. Once you repeat the words 'everyone knows that' twice it becomes circular and further repetitions are unnecessary. 'Everyone knows that' is a different type of statement to 'Alice knows that Bill knows that' or 'the day after the day after'. The latter two are linear, the first one is not. After two sets of 'everyone knows that', all of the possible connections are already made.

The Guru's statement would only provide new information if there were three or fewer people with blue eyes. That is not the case in this puzzle.

3) The hypothetical model given in the solution doesn't map to the situation as described in the puzzle. The 'solution' treats all the blue-eyed people as being connected one after the other in one long line, whereas in the puzzle they are all interconnected. So therefore, the 3rd, 4th, 5th...nth blue-eyed person are also the 2nd blue-eyed person. The maximum number of connections between any two people is one. Everyone knows that everyone with blue eyes will have the same perspective and make the same assumptions. This is common knoweldge. Nobody will expect any series of deductive reasoning to progress more than one stage removed from their own.

4) The deductive reasoning given in the 'solution' is flawed. Each stage in a line of deductive reasoning relies on the stages that come before it to remain true/possible, which is not the case here.

To get to the nth level of the deduction you need the (n-1)th level to be resolved, but resolving the (n-1)th level relies on there actually being (n-1) people with blue eyes once n>3. Deducing your eye colour if there are 3 blue-eyed people relies on there actually being three blue-eyed people, because it relies on it being possible for someone to think that someone else may see only 1 pair of blue eyes.
If there are 4 people with blue eyes, the fact that everyone sees at least 2 pairs of blue eyes is common knowledge, and so the conditions necessary for the previous level no longer exist.

To put it another way, when people are considering the case of three blue eyed people they follow a line of reasoning which makes it possible to deduce that there are precisely 3 blue eyed people. This is not the same as deducing that there are three or more people. In order to use it in further deduction it would be necessary to deduce that there were three or more people with blue eyes. The deductive logic (as described in the 'solution') works for deducing that there are '3', not '3 or more'.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Mon Jun 15, 2015 9:26 pm UTC

Arklarp, in case you missed the link in the OP, viewtopic.php?f=3&t=80149. Please look carefully at the first couple, and possibly #5 if you still aren't happy. If after reading these you still have concerns, see if you can reframe your objections to explain why they aren't addressed here, and then we can work through them as a group.

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Mon Jun 15, 2015 11:43 pm UTC

arklarp wrote:I have problems with the stated answer and the explanations so far don't seem to have resolved the issues for me. If you think I've missed any particularly good piece of explanation please let me know where it can be found so I can check to see if by some chance I have missed it or misunderstood it while reading through.

1) It seems an inescapable fact, obvious to all of us and everyone in the scenario, that none of the blue eyed people will consider leaving on the first night. This, it seems to me, instantly disproves the 'solution', because the 'solution' relies on a blue eyed person considering another blue eyed person viewing that as a possibility. The 100th person in the "A hypothesizes that B hypothesizes that C hypothesizes..." sequence still has to be someone actually in the scenario, and there is nobody who sees nobody with blue eyes. Nobody in the scenario will consider that a possibility, and so it becomes irrelevant in any deduction they could possibly make.

2) The Guru's statement does not provide any new information. The maximum amount of information that you can gain from the Guru's statement is that it ensures that everyone knows that everyone knows that the Guru sees someone with blue eyes. Since everyone can already see that everyone else can see the Guru looking at someone with blue eyes, that information is already known. Once you repeat the words 'everyone knows that' twice it becomes circular and further repetitions are unnecessary. 'Everyone knows that' is a different type of statement to 'Alice knows that Bill knows that' or 'the day after the day after'. The latter two are linear, the first one is not. After two sets of 'everyone knows that', all of the possible connections are already made.

The Guru's statement would only provide new information if there were three or fewer people with blue eyes. That is not the case in this puzzle.

3) The hypothetical model given in the solution doesn't map to the situation as described in the puzzle. The 'solution' treats all the blue-eyed people as being connected one after the other in one long line, whereas in the puzzle they are all interconnected. So therefore, the 3rd, 4th, 5th...nth blue-eyed person are also the 2nd blue-eyed person. The maximum number of connections between any two people is one. Everyone knows that everyone with blue eyes will have the same perspective and make the same assumptions. This is common knoweldge. Nobody will expect any series of deductive reasoning to progress more than one stage removed from their own.

4) The deductive reasoning given in the 'solution' is flawed. Each stage in a line of deductive reasoning relies on the stages that come before it to remain true/possible, which is not the case here.

To get to the nth level of the deduction you need the (n-1)th level to be resolved, but resolving the (n-1)th level relies on there actually being (n-1) people with blue eyes once n>3. Deducing your eye colour if there are 3 blue-eyed people relies on there actually being three blue-eyed people, because it relies on it being possible for someone to think that someone else may see only 1 pair of blue eyes.
If there are 4 people with blue eyes, the fact that everyone sees at least 2 pairs of blue eyes is common knowledge, and so the conditions necessary for the previous level no longer exist.

To put it another way, when people are considering the case of three blue eyed people they follow a line of reasoning which makes it possible to deduce that there are precisely 3 blue eyed people. This is not the same as deducing that there are three or more people. In order to use it in further deduction it would be necessary to deduce that there were three or more people with blue eyes. The deductive logic (as described in the 'solution') works for deducing that there are '3', not '3 or more'.


1) As you proceed down the chain toward the 100th person, you get further and further away from reality - if this were an xkcd strip, you'd be looking at nested thought-bubbles, with the same group of brown-eyed people, a growing group of people with question-marks for eyes and a shrinking group of blue-eyed people in each layer as you go deeper. When A hypothesises about what B hypothesises about what C hypothesises, he doesn't know what colour eyes B knows that A has, so A can't fill in that blank - and he knows that B doesn't know his own eye colour, so he knows B will have to leave those blank in his hypotheses, and he knows that B knows that C doesn't know his own eye colour, so A knows that B knows that C will leave C's eye-colour blank in his hypotheses, and so on. When the chain gets 100 deep, there are no blue eyes left, and 100 unknown pairs of eyes.

2) If everyone knows that everyone knows that there is someone with blue eyes, then that means that Alice must know that Bill knows that there's someone with blue eyes, but it doesn't tell you whether or not Alice knows that Bill knows that Carol knows that there's someone with blue eyes - that would be a special case of everyone knowing that everyone knows that everyone knows that there is someone with blue eyes - which isn't covered when you only go two deep. In the Alice knows that Bill knows that Carol knows that there's someone with blue eyes, the Alice-Bill link is different from the Bill-Carol link - the former is knowledge about knowledge about knowledge; the latter only knowledge about knowledge.

3) The solution picks one path into the deep hypotheticals, but all the other paths are equally valid. The thing is, when A thinks about B thinking about C, that's different from A thinking about C directly - A and C both know B's eye-colour, so when A thinks about C, that hypothetical C knows B's eye colour too, while A knows that B doesn't know his own eye colour, so, when A thinks about B thinking about C, that hypothetical C doesn't know what B's eye colour is because that hypothetical C only knows what the hypothetical B knows that C knows.

4) So are you saying that if there are 4 people with blue eyes, it ceases to be true that if there were only 3 people with blue eyes, they would be able to deduce their own eye-colour and leave on the third night? Does something change about the way logic works so that when there are only 3 people with blue eyes, they will leave on the third night, except when the people working out what would happen are four blue-eyed islanders?

If the four blue-eyed islanders can work out what would happen on the third night if there were only three blue-eyed islanders, what can they deduce on the fourth day?

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Wildcard » Tue Jun 16, 2015 7:37 am UTC

arklarp wrote: If you think I've missed any particularly good piece of explanation please let me know where it can be found so I can check to see if by some chance I have missed it or misunderstood it while reading through.
I'll give it a shot.

arklarp wrote: Once you repeat the words 'everyone knows that' twice it becomes circular and further repetitions are unnecessary. 'Everyone knows that' is a different type of statement to 'Alice knows that Bill knows that' or 'the day after the day after'. The latter two are linear, the first one is not. After two sets of 'everyone knows that', all of the possible connections are already made.
I'll just address this one with a quote from myself, a little further up this same page:
Wildcard wrote:Can you understand how the following sentence could be true? (It's an example.)
Everyone knows that everyone knows [some fact], but not everyone knows that everyone knows that everyone knows [that fact].
Here is a way that could happen: A staff payroll list is sent to the company president, but the entire employee email list is accidentally added to the BCC line. Now everyone knows the payroll list, but they don't know that everyone else knows it. The president meets with each person privately and lets them know that the entire company received that email—but doesn't tell them he is having this meeting with everyone. Now everyone knows that everyone knows the payroll list, but they don't know that everyone else knows that everyone knows the payroll list. (I got this example years ago on this same forum; I didn't make it up. If I remembered who posted it I would give attribution.)
Do you see now that it does not become circular after two repetitions?

arklarp wrote:4) The deductive reasoning given in the 'solution' is flawed. Each stage in a line of deductive reasoning relies on the stages that come before it to remain true/possible, which is not the case here.
I think you have "deductive" and "inductive" mixed up. Do you understand the following terms as they are understood in the realm of formal logic? The terms are:
Base case
Inductive hypothesis
Proof by induction

This is worth reading up on for the sake of fully understanding the proof, because it is very definitely not "deductive" reasoning, it is inductive, and the difference is not trivial. But I'll try to address some other statements directly:

arklarp wrote:Deducing your eye colour if there are 3 blue-eyed people relies on there actually being three blue-eyed people, because it relies on it being possible for someone to think that someone else may see only 1 pair of blue eyes.
This is actually not true. You don't have to get hypothetical at all. Here's a question that may prove fruitful: Which of the following numbered statements is false? Where does the logic break down?

1. If there is only one blue eyed person, he will leave on the first night.
He will see that no one else around has blue eyes. Therefore he will know the Guru must be talking about him, and he will leave.
Since all the inhabitants are perfect logicians, we also get:
1a. All the inhabitants on the island know statement 1 is true.
Given 1a, what happens if there are two people with blue eyes? Each brown eyed inhabitant knows that there are either 2 or 3 people with blue eyes. Each blue eyed inhabitant knows there are either 1 or 2 people with blue eyes. The uncertainty in each of these tallies is because no inhabitant knows his/her own eye color. When the first night passes and the two blue eyed people observe that the other blue eyed person is still there, they recall statement 1 above, and we get:
2. If there are two blue eyed people, they will leave on the second night.
2a. Every inhabitant knows statement 2 is true.

Another concept that might be helpful here is the definition of a "contrapositive." As an example: "If a man lives his whole life in China, he will not speak fluent unaccented English. Therefore, if a man speaks fluent unaccented English, he did not live his whole life in China." This is a contrapositive: if the original premise is true, the contrapositive is also true. So writing contrapositives for statements 1 and 2 above, we get:

1b. If no one leaves on the first night, then the number of blue eyed people is not one.
2b. If no one leaves on the second night, then the number of blue eyed people is not two.


Notice that 2b doesn't indicate anything about the number of blue eyed people other than that it is NOT two.

Continuing now, we see that if there are 3 blue eyed people, each knows that the number of blue eyed people is either 2 or 3. When no one leaves the second night, they know from statement 2b that the number of blue eyed people is not 2, so it must be 3, which means each knows his own eye color must be blue. Thus we get:
3. If there are 3 blue eyed people, they will leave on the 3rd night.
And, 3b. If no one leaves on the 3rd night, then the number of blue eyed people is not 3.

Now if there are 4 blue eyed people, each blue eyed person knows that the number of blue eyed people is either 3 or 4, depending on own eye color. But when the 3rd night passes with no one leaving, each one knows from 3b that the number of blue eyed people is not 3. At this point, according to you, no one concludes their own eye color, and statement 4 is false.

4. If there are 4 blue eyed people, they will leave on the 4th night.

Can you find any flaw in this line of reasoning? Can you examine it a little further and see how it might be the case?
There's no such thing as a funny sig.

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby SPACKlick » Tue Jun 16, 2015 9:01 am UTC

I find it best to think of where uncertainty enters the chain. Any chain with "Alice Knows" is uncertain about Alice's eye color. Any chain with "Bob knows" adds uncertainty about Bob's eye color. With "Everyone knows" you simply have 1 chain for each person and so each chain has one eye color of uncertainty. Each everyone knows you add multiplies the number of chains by the number of people (minus 1 if you exclude alice knows that alice knows). And this adds one more eye color of uncertainty for those chains where all members are different and blue eyed. For the 100 blue eyes problem a chain with 99 blue eyed people in it has 99 levels of uncertainty so that chain has knowledge only of 1 blue eyed person and uncertainty about 99 so can only know that there are between 1 and 100 inclusive blue eyed people.

The chain with all 100 blue eyed people in it ranges from 0 to 100 but with the additional knowledge from the guru the possibility of 0 blue eyed people can be excluded so in this hypothetical island the last member of the chain must have blue eyes, and must know they have blue eyes and must leave night 1.

For there the turtles stack and everyone with blue eyes leaves on the night of that number of blue eyes.

arklarp
Posts: 3
Joined: Sun Jun 14, 2015 6:52 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby arklarp » Tue Jun 16, 2015 4:59 pm UTC

Thanks for the help folks.

Gwydion wrote:Arklarp, in case you missed the link in the OP, . Please look carefully at the first couple, and possibly #5 if you still aren't happy. If after reading these you still have concerns, see if you can reframe your objections to explain why they aren't addressed here, and then we can work through them as a group.

Yes, thanks, I've read through all of those explanations but they didn't help.
I disagree with #1 and #2 because I think you can add an arbitrary number of 'everyone knows that' statements. Once you have two, it's circular. 'Everyone knows that' is not a linear connection.
I disagree with #3 because it uses the reasoning that I think is flawed. I agree that the initial statement "A should know that B knows that C sees at least 98 blue eyes, because A can see that B can see C seeing the 98 other blue eyes." is false. However, the reasoning sequence relies on the assumption that there are only 99 pairs of blue eyed people, and nobody can make that assumption. There is always the possibility that there are 100, in which case the conditions necessary for the next logical step to work are no longer there.
I disagree with #4 because the number of hypotheticals is irrelevant past two. Even if you have 100 nested statements, you are still left with a situation where one islander thinks that it is possible another islander may see no blue eyed people. That situation is clearly not possible.
I'm fine with #5. It does work for 3.
I disagree with #6 because I think we're back to faulty logic again. If you accept that everyone knows that there is no way anyone would have considered leaving on the first night, there is no reason to expect anyone to leave on the second, third or nth night either. The fact that no one leaves on the first night is not new information to anyone. Everyone from B, to C, all the way to CV, have to be treated as the same person, because they all have the same perspective. What one of them theorises is the same as what the others theorise. The reasoning in the 'solution' relies on A considering that B may think that C has a chance of leaving on the first night, which doesn't exist once there are four people with blue eyes.

Once you get to 4 or more people, the 'solution' seems to rely on the fact that everyone considers it possible that someone else may leave on the first night. Everyone's thinking "Not me, but maybe someone else". However, since everyone knows that everyone is in the same situation, everyone knows that nobody will consider leaving on the first night.

rmsgrey wrote:1) As you proceed down the chain toward the 100th person, you get further and further away from reality - if this were an xkcd strip, you'd be looking at nested thought-bubbles, with the same group of brown-eyed people, a growing group of people with question-marks for eyes and a shrinking group of blue-eyed people in each layer as you go deeper. When A hypothesises about what B hypothesises about what C hypothesises, he doesn't know what colour eyes B knows that A has, so A can't fill in that blank - and he knows that B doesn't know his own eye colour, so he knows B will have to leave those blank in his hypotheses, and he knows that B knows that C doesn't know his own eye colour, so A knows that B knows that C will leave C's eye-colour blank in his hypotheses, and so on. When the chain gets 100 deep, there are no blue eyes left, and 100 unknown pairs of eyes.

I agree that as the chain progresses you get further from reality, however since everyone knows that, that seems to me to be indicative of a fairly significant problem. Nobody is going to consider the effect of something they know to be impossible in reality.
A knows that B knows that C will leave C's eye colour undetermined in their hypothesis, however A also knows that B knows that C won't leave B or A's eye colour blank in their hypothesis. The maximum number of blanks in any person's hypothesis is 1. The maximum number of steps before every blue eyed person is accounted for is 1.
See my reply to Gwydion above, also. Everyone will instantly know that they themselves can't consider leaving on the first night. They will also all instantly realise that nobody else will consider leaving the first night. They will also all instantly realise that everyone knows this. They all instantly realise that nobody (that actually exists (in the puzzle)) will acquire any new information after the first night.

rmsgrey wrote:2) If everyone knows that everyone knows that there is someone with blue eyes, then that means that Alice must know that Bill knows that there's someone with blue eyes, but it doesn't tell you whether or not Alice knows that Bill knows that Carol knows that there's someone with blue eyes - that would be a special case of everyone knowing that everyone knows that everyone knows that there is someone with blue eyes - which isn't covered when you only go two deep. In the Alice knows that Bill knows that Carol knows that there's someone with blue eyes, the Alice-Bill link is different from the Bill-Carol link - the former is knowledge about knowledge about knowledge; the latter only knowledge about knowledge.

The Alice-Bill link is different from the Bill-Carol link, I agree. However, the Bill-Carol link is the same as the Carol-Dave link. Alice knows that Bill's perspective on Carol is the same as Carol's perspective on Dave, and that it is also the same as Carol's perspective on Bill, and Dave's perspective on Bill.
rmsgrey wrote:3) The solution picks one path into the deep hypotheticals, but all the other paths are equally valid. The thing is, when A thinks about B thinking about C, that's different from A thinking about C directly - A and C both know B's eye-colour, so when A thinks about C, that hypothetical C knows B's eye colour too, while A knows that B doesn't know his own eye colour, so, when A thinks about B thinking about C, that hypothetical C doesn't know what B's eye colour is because that hypothetical C only knows what the hypothetical B knows that C knows.

I disagree. The hypothetical C knows everything that hypothetical B knows that hypothetical C knows, plus the colour of hypothetical B's eyes. For that matter, both hypothetical B and hypothetical C also know the colour of A's eyes. Both A and Hypothetical B don't know what colour their own eyes are, but they know that hypothetical C does know.
The amount of knowledge that each person in the sequence has is the same, but person A's uncertainty about what that knowledge is increases with every step.

rmsgrey wrote:4) So are you saying that if there are 4 people with blue eyes, it ceases to be true that if there were only 3 people with blue eyes, they would be able to deduce their own eye-colour and leave on the third night? Does something change about the way logic works so that when there are only 3 people with blue eyes, they will leave on the third night, except when the people working out what would happen are four blue-eyed islanders?

If the four blue-eyed islanders can work out what would happen on the third night if there were only three blue-eyed islanders, what can they deduce on the fourth day?

What I think I'm saying is that if there are 4 people with blue eyes then there are no longer 3 people with blue eyes, and no one can use logic based on there being a maximum of 3 people with blue eyes.

Wildcard wrote:I'll give it a shot.
I'll just address this one with a quote from myself, a little further up this same page:
...
Do you see now that it does not become circular after two repetitions?

Thanks, but I had read that already, and no, that doesn't seem to affect my stance. I don't think that your example maps to the puzzle situation. Everyone in the puzzle knows that everyone is a perfect logician. Therefore, everyone knows that any realisation that any of them have, every other person in the same situation will also have. This is what results in the potential for infinite repetitions of 'everyone knows that'. Everyone knows that everyone can see someone with blue eyes. Since everyone's the same, everyone knows that everyone will have that realisation. For the same reason, everyone knows all of that. etc. etc. ad infinitum. In the puzzle, because all knowledge is shared knowledge, it is circular.

Wildcard wrote:I think you have "deductive" and "inductive" mixed up. Do you understand the following terms as they are understood in the realm of formal logic? The terms are:
Base case
Inductive hypothesis
Proof by induction

This is worth reading up on for the sake of fully understanding the proof, because it is very definitely not "deductive" reasoning, it is inductive, and the difference is not trivial.

The quick answer is no. However, I think I may have used the word deductive correctly. Wikipedia seems to agree with me that there is no such thing as proof by induction. For anyone to be sure of their own eye colour, it needs to be the only possible option, and that seems to be deduction not induction.
However I don't think the names of the types of reasoning are central to the problems I'm encountering.

Wildcard wrote:This is actually not true. You don't have to get hypothetical at all. Here's a question that may prove fruitful: Which of the following numbered statements is false? Where does the logic break down?

I think the problems start with statement 3. Statement 2b is fine: If no one leaves on the second night, the number of people is not two. However, your reasoning to get to statement 3 includes the statement "each knows that the number of blue eyed people is either 2 or 3", and that relies on the fact that there are no more than 3 people with blue eyes. If there are 4 people with blue eyes, then nobody can know that the number of people is either 2 or 3.
If there are 3 people then everyone leaves on night three, but nobody can be sure of what happens if there are 4 people.


What happens, specifically, if there are 4 people with blue eyes?
Which specific person expects someone to leave on the first night? Nobody.
Which person, specifically, doesn't know that the Guru can see someone with blue eyes before the Guru speaks? The answer is nobody, and everyone knows this.
Which person thinks that there may be someone who doesn't know the Guru can see someone with blue eyes? The answer to this one is also nobody, and again, everyone knows this.
If anyone knows the previous statement, then everyone knows it, because everyone is in the same situation with the same abilities.

Are any of these statements incorrect?

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Tue Jun 16, 2015 5:48 pm UTC

arklarp wrote:What happens, specifically, if there are 4 people with blue eyes?
Which specific person expects someone to leave on the first night? Nobody.
Which person, specifically, doesn't know that the Guru can see someone with blue eyes before the Guru speaks? The answer is nobody, and everyone knows this.
Which person thinks that there may be someone who doesn't know the Guru can see someone with blue eyes? The answer to this one is also nobody, and again, everyone knows this.
If anyone knows the previous statement, then everyone knows it, because everyone is in the same situation with the same abilities.

Are any of these statements incorrect?


No actual person expects someone to leave on the first night, but there are 24 second-level virtual people who expect someone to leave on the first night - A's model of B's model of C, A's model of B's model of D, A's model of C's model of B, A's model of C's model of D, A's model of D's model of B, A's model of D's model of C, B's model of A's model of C, B's model of A's model of D, B's model of C's model of A, B's model of C's model of D, B's model of D's model of A, B's model of D's model of C, C's model of A's model of B, C's model of A's model of D, C's model of B's model of A, C's model of B's model of D, C's model of D's model of A, C's model of D's model of B, D's model of A's model of B, D's model of A's model of C, D's model of B's model of A, D's model of B's model of C, D's model of C's model of A, and D's model of C's model of B.

It's just like in the 3 person case, where there are 6 first-level virtual people who expect someone to leave on the first night, but no actual people. This also shows why we tend to pick out just one path and talk about the modelling on that, because listing multiple paths gets kinda dull and doesn't add much, and gets kinda confusing too.

There are also 24 third-level virtual people for each brown-eyed islander who expect someone to leave on the first night - and an infinite number of deeper-level virtual people (such as A's model of B's model of A's model of B's model of C).

There are no real people who don't know that the guru can see blue eyes before they speak, but there are 24 third-level virtual people (A's model of B's model of C's model of D, etc). With as few as 2 blue-eyed islanders, there are no real people who don't know that the guru can see blue eyes before they speak.

There are no real people who think there could be someone who didn't already know that the guru can see blue eyes, but there are 24 second-level virtual people who do (A's model of B's model of C, etc) - precisely the virtual people who think someone might leave on the first night.


While everyone is in the same situation with the same abilities, not everyone has the same information, so any two people only know exactly the same things when they don't rely on secrets that one knows and the other doesn't, so they can come to different conclusions.

arklarp
Posts: 3
Joined: Sun Jun 14, 2015 6:52 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby arklarp » Tue Jun 16, 2015 8:13 pm UTC

rmsgrey wrote:There are no real people who think there could be someone who didn't already know that the guru can see blue eyes, but there are 24 second-level virtual people who do (A's model of B's model of C, etc) - precisely the virtual people who think someone might leave on the first night.

For me, the problem seems to come when the people in the puzzle try and use these virtual people to make decisions.
These virtual people are in a situation that (it is universally acknowledged) does not and cannot exist, responding to new information that also doesn't and cannot exist. I don't see how anyone can infer, deduce or induce anything relevant from these entirely fictional virtual people. It seems that the 'solution' relies on a perfectly logical person choosing to act based on drawing parallels between two situations they know to be contradictory. At some point, it seems everyone has to make the transfer from hypothetical fiction to reality, and I don't see why (or how) anyone can do that and maintain any kind of certainty.

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby SPACKlick » Tue Jun 16, 2015 8:21 pm UTC

Imagine it's about not being accused of having the cookie

I know I don't have the cookie. If I assume everyone else knows that then I am safe but that's not the case.
If everyone is shown I don't have the cookie one by one
I know that Bob knows I don't have the cookie.
I can form an alliance with bob about looking for other suspects, including bob.
Bob and chris cannot form such an alliance because
Bob doesn't know that chris knows I don't have the cookie.
So my predictions of Bob and Chris's actions require me to understand Bob's mental image of Chris.
Bob's mental image of christ contains uncertainties I don't have
ie. I know chris knows I don't have the cookie but Bob doesn't so Bob's mental representation of Chris could accuse me of having the cookie even though I know Chris would never do that.
If Chris Tells Bob that he knows I don't have the cookie then bob does know that chris knows that I don't have the cookie, so Bob's mental predictions fr chris will no longer predict that he could accuse me.
I don't know that so my mental representation of Bob has a mental representation of Chris which might accuse me even though Me Chris and Bob all know I don't have the cookie.

As you get further nested you add further uncertainties. Just because at one level nobody is uncertain about my ownership of the cookine doesn't mean that at nested levels that uncertainty can't appear because of uncertainty about knowledge of that knowledge.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Gwydion » Tue Jun 16, 2015 8:42 pm UTC

arklarp wrote:
rmsgrey wrote:There are no real people who think there could be someone who didn't already know that the guru can see blue eyes, but there are 24 second-level virtual people who do (A's model of B's model of C, etc) - precisely the virtual people who think someone might leave on the first night.

For me, the problem seems to come when the people in the puzzle try and use these virtual people to make decisions.
These virtual people are in a situation that (it is universally acknowledged) does not and cannot exist, responding to new information that also doesn't and cannot exist. I don't see how anyone can infer, deduce or induce anything relevant from these entirely fictional virtual people. It seems that the 'solution' relies on a perfectly logical person choosing to act based on drawing parallels between two situations they know to be contradictory. At some point, it seems everyone has to make the transfer from hypothetical fiction to reality, and I don't see why (or how) anyone can do that and maintain any kind of certainty.

Let's take this back to the start. You're on this island (you have brown eyes), and you see two people with blue eyes. You know they both see each other, so they know blue eyes exist. When the guru speaks, none of them leave that night. They take this bit of information, and they correctly deduce that they must both have blue eyes - after all, they each see 1 blue eyed islander, so if they themselves didn't have blue eyes the other islander would have left that first night.

Now, let's say you don't know your eye color. None of you will leave the first night, of course - everybody can see a blue eyed islander, and you know this to be true so you don't expect any different. If your eyes are not blue, then we are in the situation above and the other two will leave on night 2. Imagine being in islander A's shoes, however - she doesn't know her eye color, and if your eyes are blue (you don't know) she will see the same situation as above as well. She might be expecting that you and Islander B will leave on night 2, and islander B might have the same thought. It feels like you've learned nothing new about the situation, but when you are all still there on morning 3 you know you all have blue eyes. This is because the hypothetical scenarios that you're all playing out in your heads have been proven false by virtue of nobody leaving. All 3 of you will leave on night 3.

Here are some questions to ponder:
1) Does this make sense? Your previous comments suggest that you agree that three islanders can determine their eye color based on the above logic, but just making sure.
2) Imagine I'm on the island with you, and I have brown eyes. Does my presence change anything about your mental framework? Do you still leave on the third night?
3) Imagine I'm on the island with you, and I have blue eyes. Does this change anything? Do you still leave on the third night? If so, how? If not, why not?
4) If these situations are different, and I can detect this difference based on whether you leave on night 3, why can't I use that information to determine whether my eyes are blue on morning 4?

rmsgrey
Posts: 3259
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby rmsgrey » Tue Jun 16, 2015 9:37 pm UTC

arklarp wrote:
rmsgrey wrote:There are no real people who think there could be someone who didn't already know that the guru can see blue eyes, but there are 24 second-level virtual people who do (A's model of B's model of C, etc) - precisely the virtual people who think someone might leave on the first night.

For me, the problem seems to come when the people in the puzzle try and use these virtual people to make decisions.
These virtual people are in a situation that (it is universally acknowledged) does not and cannot exist, responding to new information that also doesn't and cannot exist. I don't see how anyone can infer, deduce or induce anything relevant from these entirely fictional virtual people. It seems that the 'solution' relies on a perfectly logical person choosing to act based on drawing parallels between two situations they know to be contradictory. At some point, it seems everyone has to make the transfer from hypothetical fiction to reality, and I don't see why (or how) anyone can do that and maintain any kind of certainty.


Look at the situation with just 2 blue-eyed people, A and B. They both know already that the guru can see someone with blue eyes. A has two possible models of B - one where B sees A having blue eyes, and one where B sees A having some other colour eyes. So A reasons that if B is the only blue-eyed person, B would not already know that the guru could see someone with blue eyes, and so B would deduce his own eye colour and leave the island overnight. When B doesn't leave, A can eliminate the model of B where A has non-blue eyes, so knows he must have blue eyes too, and leaves on the second night.

With 3 blue-eyed people, A, B and C, A models B and C as being in the 2 blue-eyed person situation (or 3 blue-eyed with A), so expects B to model C as the only blue-eyed islander as above, and then when C doesn't leave on the first night (as A and B both knew he wouldn't, but A's model of B didn't know would happen), A's models of B and C where A has non-blue eyes would deduce their own eye colours, and both leave on the second night. When that doesn't happen, A can eliminate the models of B and C where A doesn't have blue eyes, so knows he must have blue eyes too and leaves on the third night.

With 4 blue-eyed people, again, A models the other blue-eyed people as being the only blue-eyed people, so models B, C and D as being in the 3 blue-eyed islander situation, and models B as modelling C and D as being in the 2 blue-eyed person situation, where the model-B models C as modelling D as the only blue-eyed person. When, as A, B, C, model-B and model-C all knew would happen, D doesn't leave, model-model-C concludes that the model-model-model-D who is the lone blue-eyed person on the island is not possible, so model-model-C concludes that he also has blue eyes (as does model-model-D). On the second night, when neither C nor D leaves, as A and B both knew would happen, but model-B didn't, model-B deduces that he has blue eyes (as do model-C and model-D) and leaves on the third night. When B C and D all stay, which A didn't know was going to happen (though the rest of the islanders did), A deduces that there weren't exactly 3 blue-eyed islanders, so he must have blue eyes himself (likewise, B, C and D, who've been doing their own modelling reach the equivalent conclusions about themselves) and all four of them leave on the fourth night.


Keeping the layers of hypotheticals straight adds an increasing amount of clutter to the argument without making it much clearer. Another way of looking at it is to consider a chain of 101 islands, each of which has 100 islanders on, each with a different number of blue-eyed islanders, from 0 to all 100. No-one knows which island they're on, until a guru comes and announces publicly (maybe by some kind of satellite linkup? what matters is that the announcement is common knowledge) which is island #0, the only island with no blue-eyed islanders. Immediately, on island #1, the lone blue-eyed islander who knew he was on either #0 or #1 deduces he is on #1 and leaves that night. The following day, the blue-eyed pair on island #2, who knew they were on either island #1 or island #2 deduce that they're not on #1, so leave that night, and so on.

As long as you believe that the blue-eyed people on island #69 will leave on the 69th night, and accept that, since you can work that out, so can the people on island #70, you can deduce that the blue-eyed people on island #70 will be able to deduce that they're not on island #69 when no-one leaves on the 69th night, and, since they knew they were either on #69 or #70, they know they're on #70 and leave that night, the 70th night. It doesn't have to be 69 and 70, of course - any two consecutive numbers will work.

In particular, if you are on one of these islands and believe you have proven that the 3 blue-eyed islanders on island #3 will leave on the third night, then, if you see 3 blue-eyed islanders not counting yourself, you can deduce that either you're on island #3 or island #4 and you'll be able to tell it isn't #3 if no-one leaves on the third night.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby Wildcard » Wed Jun 17, 2015 2:45 am UTC

arklarp wrote:Thanks for the help folks.

You're welcome.

arklarp wrote:
Wildcard wrote:This is actually not true. You don't have to get hypothetical at all. Here's a question that may prove fruitful: Which of the following numbered statements is false? Where does the logic break down?

I think the problems start with statement 3. Statement 2b is fine: If no one leaves on the second night, the number of people is not two. However, your reasoning to get to statement 3 includes the statement "each knows that the number of blue eyed people is either 2 or 3", and that relies on the fact that there are no more than 3 people with blue eyes. If there are 4 people with blue eyes, then nobody can know that the number of people is either 2 or 3.
If there are 3 people then everyone leaves on night three, but nobody can be sure of what happens if there are 4 people.

Okay, great. Thanks for answering.

Let's examine the logic a little further between 2b and 3.

2b: If no one leaves on the second night, then the number of blue eyed people is not two.

I'll assume you already noted the parallels between statement 1b, and 2b, and 3b. And the parallels between 1a and 2a, and so on. There are actually a few other chains that are relevant but which I omitted.

1c. If there is one blue eyed person on the island, he knows (before the Guru ever speaks) that the number of blue eyed people on the island is either 0 or 1.
1d. If there is one blue eyed person on the island, each brown eyed person knows that the number of blue eyed people on the island is either 1 or 2.

2c. If there are two blue eyed people on the island, each blue eyed person knows that the number of blue eyed people on the island is either 1 or 2.
2d. If there are two blue eyed people on the island, each brown eyed person knows that the number of blue eyed people on the island is either 2 or 3.

3c. If there are 3 blue eyed people on the island, each blue eyed person knows that the number of blue eyed people on the island is either 2 or 3.
3d. If there are 3 blue eyed people on the island, each brown eyed person knows that the number of blue eyed people on the island is either 3 or 4.

4c. If there are 4 blue eyed people on the island, each blue eyed person knows that the number of blue eyed people on the island is either 3 or 4.
4d. If there are 4 blue eyed people on the island, each brown eyed person knows that the number of blue eyed people on the island is either 4 or 5.


Are you with me on these? Any arguments about them? Good. (I'm assuming not; if you do have any objection to them then by all means, let me know.)

So, based on 4c and 3b:
4c. If there are 4 blue eyed people on the island, each blue eyed person knows that the number of blue eyed people on the island is either 3 or 4.
3b. If no one leaves on the 3rd night, then the number of blue eyed people is not 3.

If there are 4 blue eyed people, what does each blue eyed person conclude after no one leaves on the 3rd night?

(Also with the statements organized like this, it's easy to see why the brown eyed people don't conclude the same thing—because by 4d, they know the number of blue eyed people is either 4 or 5, so 3b doesn't tell them anything new.)
There's no such thing as a funny sig.

User avatar
phlip
Restorer of Worlds
Posts: 7550
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Postby phlip » Wed Jun 17, 2015 3:09 am UTC

arklarp wrote:Wikipedia seems to agree with me that there is no such thing as proof by induction.

I think you may be mixing up mathematical induction with inductive reasoning. It's the first one that is being used here, and it's an entirely valid form of proof. The second one is the one that gets contrasted with deductive reasoning, and doesn't work as a mathematical proof. The two concepts aren't really connected other than the similar names, and in fact mathematical induction is a form of deductive reasoning, not inductive. (Wildcard also seems to have gotten the two terms mixed up, which probably didn't help.)


An important thing to consider with the induction proof of this puzzle is that it doesn't matter that some of the arguments being used to support one case are no longer applicable as you move to the next case... because the only thing that needs to transfer from one case to the next is that "if there are n blue-eyed people, they'll leave on night n" is true. It doesn't matter how it's proven, just that it's true. Even if there are some arguments that are only applicable to the n-person case and which don't apply in the (n+1)-person case, that doesn't matter, because the statement is about the n-person case... and when we're considering the (n+1)-person case we only care that the statement is true about the n-person case.

Say, for instance, you accept that it's true for the 3-person case... you accept that if there are three blue-eyed people they'd leave on night three. This is a universal truth, and being perfect logicians, everyone on the island will know this, regardless of how many blue-eyed people there actually are. There could be a million blue-eyed people on the island, but everyone on the island would still know the counterfactual "if there were instead 3 blue-eyed people, they'd leave on night 3". So, with that established, now we consider the 4-blue-eyes case. Each blue-eyed person would think "if my eyes aren't blue, then there are three blue eyed people on the island, and as we've just discussed, they'll leave on night 3". Then when they don't leave on night 3, they can deduce that their eyes must be blue. They don't need to depend on any details of how the "3 blue-eyes leave on night 3" fact was deduced, they only need to depend on the fact that it's true. And so, we have that "if there are 4 blue-eyed people they will leave on night 4"... and, similarly, this is a mathematical truth, and if we were able to deduce it, then the perfect logicians on the island are able to deduce it, regardless of how many blue-eyed people there actually are. And so the induction continues.


An alternative way of looking at all this induction stuff: what's the smallest example where it fails? What's some n where if there are n blue-eyed people would leave the island on night n, but n+1 would not leave on night n+1? And how do those n+1 people avoid seeing their n colleagues not leave on night n, and deducing their eyes must be blue?


Jumping gears to the nested-hypotheticals angle (which, to be clear, is a completely separate proof to to the induction proof... either of which would be enough to solve the problem on its own, they're just two different ways of attacking the problem... the induction proof is easier to understand, but less intuitively satisfying, while the nested-hypotheticals proof is more complex but answers the "what information does the guru give" question).
arklarp wrote:For me, the problem seems to come when the people in the puzzle try and use these virtual people to make decisions.
These virtual people are in a situation that (it is universally acknowledged) does not and cannot exist, responding to new information that also doesn't and cannot exist.

At no point in the nested hypotheticals does anyone consider a hypothetical that they personally know is incorrect. Every hypothetical is something that, for all the person considering the hypothetical knows, is possible.

For instance, say there are 4 blue-eyed people on the island, call them A, B, C and D.
A can think "what if my eyes are brown? then there are 3 blue-eyed people on the island" - we know this is incorrect, there are actually 4 blue-eyed people, but A doesn't, and they can consider the possibility.
A can think "what if my eyes are brown? then B could be thinking 'what if my eyes are green? then there are 2 blue-eyed people on the island'" - we know this is incorrect, and B is actually not thinking that, but A doesn't know this. Because in the nested hypothetical, we know it's incorrect, and A knows it's incorrect, and B knows it's incorrect, but A doesn't know B knows it's incorrect, so the B inside A's hypothetical doesn't know it's incorrect, because A's hypothetical is about the situation where B doesn't know it's incorrect.

That is: A's hypothetical B is considering the possibility that there are 2 blue-eyed people, and A's hypothetical B doesn't know that to be incorrect.
Meanwhile, A is considering the possibility that B is considering that, and A doesn't know that B actually isn't considering that.

And we can go deeper.
A can think "what if my eyes are brown? then B could be thinking 'what if my eyes are green? then C could be thinking "what if my eyes are purple? then there is only 1 blue-eyed person on the island."'".
We know that B isn't thinking that, but A doesn't.
Because we know that C isn't thinking that, and the real B knows that C isn't thinking that, but A doesn't know that B knows that.
Because we know there's more than 1 blue-eyed person on the island, and the real C knows it, and the real B knows that the real C knows it, and even A knows that the real C knows it, but A doesn't know that the real B knows that the real C knows it.

We can keep going deeper - the maths still works, it just becomes harder to parse when it's spelled out in words (English needs more than two pairs of quote marks).

There's no hypotheticals there where the person actually making the hypothetical knows it to be incorrect.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 3 guests