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

41–50 of 94 posts

Re: Blue Eyes Logic Puzzle

#41

Post by Mindless2112 »

IanDrake wrote: post #27
Mindless2112 wrote: post #12

Earlier quoted context omitted.

Each blue-eyed person observes 99 other blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 100th day. However, each brown-eyed person observes 100 blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 101st day (however this does not happen because on the 100th day all the blue-eyed people commit ritual suicide.)

Doesn't that presuppose they know there are 100 blue eyed people in their tribe? When that information is presented to the reader, it's presented as outside knowledge. If they knew the color counts, they would know their eye color and all would have to commit suicide. The fact that the tribe still existed means, they didn't know the totals. For example, if I know there are 100 people with blue eyes and I can count as…

It is not necessary for the blue-eyed people to know the total number of blue-eyed people in the tribe, they can deduce it at day 100:

  * A blue-eyed person observes 99 blue-eyed people.
  * On day 99, the blue-eyed people do not commit ritual
    suicide.
  * Thus each blue-eyed person learns that all the blue-eyed
    people also observe 99 blue-eyed people.
  * Thus the blue-eyed person knows that the other blue-eyed
    people must observe that he/she has blue eyes.

Re: Blue Eyes Logic Puzzle

#42

Post by jwpeddle »

bonobo wrote: post #29
md224 wrote: post #3

Earlier quoted context omitted.

And for an even more detailed examination of the underlying philosophical issues: http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://plato.stanford.edu/entries/common-knowledge/

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…

No information is added, it just gives all islanders a synchronized reference point to sort themselves into groups. It's the synchronization that matters, not the info itself, per se. Once they all start sorting themselves on the same day (and KNOW that all other residents are doing the same) they start the countdown to day 100.

Re: Blue Eyes Logic Puzzle

#43

Post by benjohnson »

IanDrake wrote: post #27
Mindless2112 wrote: post #12

Earlier quoted context omitted.

Each blue-eyed person observes 99 other blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 100th day. However, each brown-eyed person observes 100 blue-eyed people in the tribe, thus reasoning that he/she has blue eyes on the 101st day (however this does not happen because on the 100th day all the blue-eyed people commit ritual suicide.)

Doesn't that presuppose they know there are 100 blue eyed people in their tribe? When that information is presented to the reader, it's presented as outside knowledge. If they knew the color counts, they would know their eye color and all would have to commit suicide. The fact that the tribe still existed means, they didn't know the totals. For example, if I know there are 100 people with blue eyes and I can count as…

>> The fact that the tribe still existed means, they didn't know the totals.

That's the crux of it right there.

If I may also add: the outside observers remark didn't tell the tribe any information they didn't already know - that there is a blue-eyed tribe member.

Re: Blue Eyes Logic Puzzle

#45

Post by matchu »

bonobo wrote: post #29
md224 wrote: post #3

Earlier quoted context omitted.

And for an even more detailed examination of the underlying philosophical issues: http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://plato.stanford.edu/entries/common-knowledge/

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, but nobody knows that everyone knows that. Then the foreigner comes along and tells them that, between Alice and Bob, Blue ≥ 1. Now Alice knows that Bob knows that Blue ≥ 1, and realizes that, if Alice has non-blue eyes, Bob will use the new information that Blue ≥ 1 to conclude that he has blue eyes, and therefore commit suicide on the next day. When he doesn't, she concludes that she must have blue eyes, and commits suicide. Bob goes through the exact same logic as Alice.

Though the foreigner's statement did not tell Alice anything new about eye color distribution, it did tell her something about Bob's knowledge. The same goes for Bob, who learns about Alice's knowledge.

The logic is a bit more difficult to talk through with three people, so generalizing it further is left as an exercise ;P It comes down to "everyone knows that everyone knows that Blue ≥ 1", which the foreigner also contributes as common knowledge by making his announcement. For more blue-eyed people, recur on that statement as many times as necessary.

Re: Blue Eyes Logic Puzzle

#46

Post by [deleted] »

bonobo wrote: post #29
md224 wrote: post #3

Earlier quoted context omitted.

And for an even more detailed examination of the underlying philosophical issues: http://en.wikipedia.org/wiki/Common_knowledge_(logic) http://plato.stanford.edu/entries/common-knowledge/

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…

[deleted]

Re: Blue Eyes Logic Puzzle

#47

Post by [deleted] »

hornd wrote: post #9

I think the foreigners statement is ambiguous enough to render the proof in argument 2 incorrect. "... another blue-eyed person", to me, implies a singular person in the tribe has blue eyes. All of tribespeople will see multiple tribespeople with blue eyes, and therefore assume the foreigners statement was wrong, rendering no effect.

[deleted]

Re: Blue Eyes Logic Puzzle

#48

Post by plaid_hatter »

jwpeddle wrote: post #42
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…

No information is added, it just gives all islanders a synchronized reference point to sort themselves into groups. It's the synchronization that matters, not the info itself, per se. Once they all start sorting themselves on the same day (and KNOW that all other residents are doing the same) they start the countdown to day 100.

The information that is added is that the knowledge is made common or infinite degree (ie. everyone knows that everyone knows that everyone knows......that there is someone with blue eyes)

Re: Blue Eyes Logic Puzzle

#49

Post by miahi »

spongerbakula wrote: post #44

Ok, I'm pretty sure I'm being moronic and missing something, but does the foreigner give the tribe any more information? Does the tribe already know how many blue eyed and brown eyed people there are?

If they already knew how many of each, then they would all be dead, as any of them would see that the numbers add up only if he was in a specific group.

Re: Blue Eyes Logic Puzzle

#50

Post by vytasgd »

The traveler has no effect. The logical flaw is that with n > 2 blue eyed people, everybody knows that there is at least 1 blue eyed person AND everybody knows that everybody ELSE knows that there is at least 1 blue eyed person.

The traveler's comments would only have an effect with n 2, the info is already out that blue-eyed ppl exist and the count has already started.

Post reply on HN