Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Blue Eyes Logic Puzzle

math.ucla.edu

Post reply on HN
Print view View original

81–90 of 94 posts

Re: Blue Eyes Logic Puzzle

#81

Post by pavelrub »

Mindless2112 wrote: post #75
DannoHung wrote: post #66

Earlier quoted context omitted.

I think you've got it wrong. The information added is that a blue eyed person has been positively identified. In the three person case, each blue eyed person can see two people and is internally modeling their logic about the two person scenario. Once the logic for a two person scenario falls through, they can infer that there are not two people with blue eyes. The brown eyed people are however modeling an N+1 person…

Hmm. That seems right. With 3 blue-eyed people, a blue-eyed person observing that the 2 blue-eyed people did nothing does add the additional knowledge that there are a total of 3 blue-eyed people. So the additional knowledge added for 3 or more blue-eyed people is a lower bound on the total number of blue-eyed people (which grows over time), but it's not exactly clear to me why the foreigner's statement triggers this…

The new information (common knowledge) is added immediately to everybody, not after 2 days. Using this information (that everybody knows that everybody knows that everybody knows...), it is then possible to decide whether you have blue eyes or not after 2 days.

Re: Blue Eyes Logic Puzzle

#82

Post by lisper »

voyou wrote: post #68
lisper wrote: post #18

Earlier quoted context omitted.

No, the key is that the foreigner's statement establishes common knowledge at some point in time. What happened before that point in time is irrelevant. > the blue-eyed islanders all know that there are 99 other islanders with blue eyes That's true, but what they don't know (until the 2nd) day) is that all the other blue-eyed islanders know that all the other blue-eyed islanders know that there are 99 other blue-eyed…

"what they don't know (until the 2nd) day) is that all the other blue-eyed islanders know that all the other blue-eyed islanders know that there are 99 other blue-eyed islanders." I don't see how they know that on the second day, either, though. Before the foreigner's statement, every blue-eyes islanders knows a) that there are at least 99 blue-eyed islanders b) that all the blue-eyed islanders know that there are at…

You're right, my explanation is actually wrong. The idea is right, but the recursive knowledge is not gained incrementally the way I described but rather all at once at the end when they wake up on the nth day and see that everyone is still alive.

Each one reasons (recursively) that if their eyes are brown then, given that common knowledge of the existence of blue-eyed people has been established, the remaining n-1 blue-eyed people will realize their eyes are blue (and kill themselves) on the n-1'th day. Since this doesn't happen, their eyes must be blue.

Re: Blue Eyes Logic Puzzle

#83

Post by backlava »

thaumasiotes wrote: post #54
Mindless2112 wrote: post #51

Edit: it looks like I'm wrong. The first argument is true; the second has the logical flaw. The flaw is assuming that induction can continue despite additional pre-knowledge available when there are greater numbers of blue-eyed people. The statement will have no effect when the number of blue-eyed people is 3 or more: When the number of blue-eyed people is 0, the foreigner is lying, and if the tribe believes him, eve…

I read an essay once remarking that the ancient Greeks really wanted to square the circle (you can think of the problem as being to construct a line of length pi using only a reference line of length 1 and a compass and straightedge). Despite not knowing that this couldn't be done, no reference survives to any Greek claiming that it could. Today, we know perfectly well that the problem is impossible. But we get dozen…

Oh please. The only things that have changed are access to such ideas and the volume of our records. He's already corrected his position. No harm in being wrong on the internet. Politeness is more important than rightness as a rule to enforce. Rightness sorts itself out among able and interested parties.

Re: Blue Eyes Logic Puzzle

#84

Post by thaumasiotes »

backlava wrote: post #83
thaumasiotes wrote: post #54

Earlier quoted context omitted.

I read an essay once remarking that the ancient Greeks really wanted to square the circle (you can think of the problem as being to construct a line of length pi using only a reference line of length 1 and a compass and straightedge). Despite not knowing that this couldn't be done, no reference survives to any Greek claiming that it could. Today, we know perfectly well that the problem is impossible. But we get dozen…

Oh please. The only things that have changed are access to such ideas and the volume of our records. He's already corrected his position. No harm in being wrong on the internet. Politeness is more important than rightness as a rule to enforce. Rightness sorts itself out among able and interested parties.

> The only things that have changed are access to such ideas and the volume of our records.

Both of those definitely changed; unlike some of the other things you say, this is not ridiculous. However, I can easily imagine finding in, say, the personal correspondence of Archimedes, a statement like "this idiot tried to show me another squaring-the-circle proof again". We do preserve personal correspondence in ancient records, and that sort of thing doesn't require a lot of access.

> No harm in being wrong on the internet.

http://www.mamapedia.com/article/mmr-vaccination

Money quote: "I have really close friends who swear that within 24 hours of the MMR their child had symptoms of autism"

> Politeness is more important than rightness as a rule to enforce.

It's better to be right. Enforcement of politeness greatly retards, and can prevent, the discovery / acknowledgement of rightness.

> Rightness sorts itself out among able and interested parties.

This can be tautologically true, depending on your definition of "able". It's very clear that rightness does not sort itself out among interested parties, and they can be harmed thereby.

Re: Blue Eyes Logic Puzzle

#85

Post by bonobo »

thaumasiotes wrote: post #84
backlava wrote: post #83

Earlier quoted context omitted.

Oh please. The only things that have changed are access to such ideas and the volume of our records. He's already corrected his position. No harm in being wrong on the internet. Politeness is more important than rightness as a rule to enforce. Rightness sorts itself out among able and interested parties.

> The only things that have changed are access to such ideas and the volume of our records. Both of those definitely changed; unlike some of the other things you say, this is not ridiculous. However, I can easily imagine finding in, say, the personal correspondence of Archimedes, a statement like "this idiot tried to show me another squaring-the-circle proof again". We do preserve personal correspondence in ancient r…

You missed what I think is baklava's main point: "The only things that have changed are access to such ideas and the volume of our records." Your argument that "The essay reflected that something has gone wrong in our culture" is a pretty bold statement that doesn't take into consideration the volume of and access to information we have today.

To me it seems you're contradicting yourself. What does this bold statement of yours tells you about trying to contribute to a problem one does not understand?

Re: Blue Eyes Logic Puzzle

#86

Post by thaumasiotes »

bonobo wrote: post #85
thaumasiotes wrote: post #84

Earlier quoted context omitted.

> The only things that have changed are access to such ideas and the volume of our records. Both of those definitely changed; unlike some of the other things you say, this is not ridiculous. However, I can easily imagine finding in, say, the personal correspondence of Archimedes, a statement like "this idiot tried to show me another squaring-the-circle proof again". We do preserve personal correspondence in ancient r…

You missed what I think is baklava's main point: " The only things that have changed are access to such ideas and the volume of our records ." Your argument that " The essay reflected that something has gone wrong in our culture " is a pretty bold statement that doesn't take into consideration the volume of and access to information we have today. To me it seems you're contradicting yourself. What does this bold stat…

The quote you're giving me leads my response and I describe it as "not ridiculous".

"The essay reflected that ______" reports someone else's point of view, not my own. I agree that something is wrong in our culture; it cannot be shown that this represents a change from that of Classical Greece, but it can be supposed to varying levels of certainty. But if I exhort people to stop contributing to a problem of today, whether that problem originated in the recent past or the ancient past is of no relevance. We should still stop it today.

Re: Blue Eyes Logic Puzzle

#87

Post by thaumasiotes »

vytasgd wrote: post #55
thaumasiotes wrote: post #54

Earlier quoted context omitted.

I read an essay once remarking that the ancient Greeks really wanted to square the circle (you can think of the problem as being to construct a line of length pi using only a reference line of length 1 and a compass and straightedge). Despite not knowing that this couldn't be done, no reference survives to any Greek claiming that it could. Today, we know perfectly well that the problem is impossible. But we get dozen…

Pardon? The parent's comment is correct. Edit: my comment is still correct thanks to parent's 2nd edit.

> Edit: my comment is still correct thanks to parent's 2nd edit.

If you're playing the retroactive-history game, let me point out that that edit had not been made when you made your comment. If party A issues a statement, I point out that it's nonsense, you say that you agree with party A, and then A recants, that doesn't make you right by virtue of the wording you used to agree with him. It makes you foolish.

Re: Blue Eyes Logic Puzzle

#88

Post by informatimago »

1- Nothing says that there were 1000 islanders on the day the alien made his speech. Some may have discovered they eye color and died before.

2- Compare: “how unusual it is to see another blue-eyed person like myself in this region of the world” with: “how unusual it is to see other blue-eyed persons like myself in this region of the world”

To me, it is clear that the entire tribe the day the stranger makes his speech consists of N brown-eyed, and one single remaining blue-eyed.

They immediately understand the same thing, and all commit suicide the next noon.

Re: Blue Eyes Logic Puzzle

#89

Post by thedufer »

tbrake wrote: post #34
dnautics wrote: post #32

> Now suppose inductively that n is larger than 1. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all commit suicide n-1 days after the traveler’s address”. Why should not a brown-eyed person reason as follows as well? It is at this stage that an implicit "counting" of the blue-eyed population creeps into the flawed p…

They would. The traveller has accidentally doomed them all. edit: this is based on an unfounded assumption because of the wording of the problem - they may only know they don't have blue eyes. But when I read "100 have blue eyes and 900 have brown" it makes it sound binary and I assumed that's knowledge the tribes people have as well, i.e. we have only either blue or brown eyes.

In Randall Munroe's version of the problem, he gives the visitor red eyes to explicitly avoid this binary assumption. Obviously, the visitor's statement is slightly different because of this.

Re: Blue Eyes Logic Puzzle

#90

Post by matchu »

matchu wrote: post #45
bonobo wrote: post #29

Earlier quoted context omitted.

I understand the induction steps, but what I don't get is why the foreigner's statement triggers the logic induction. This quote from your first link sums it well: What's most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge. I…

What's added is the common knowledge that everyone else knows that Blue > 1 (including the foreigner), and that everyone else knows that everyone else knows that Blue > 1, etc. Consider two blue-eyed people, Alice and Bob. Alice sees Bob's blue eyes and knows that Blue ≥ 1, and vice-versa. But Alice thinks, "What if I have brown eyes? In that case, Bob wouldn't know that Blue ≥ 1." So, everyone knows that Blue ≥ 1, b…

Small clarification: For the two-person case, it's important that everyone knows that everyone knows that Blue ≥ 1. For the three-person case, it's important that everyone knows that everyone knows that everyone knows that Blue ≥ 1. (The last paragraph is a bit unclear and/or wrong.)
Post reply on HN