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

71–80 of 94 posts

Re: Blue Eyes Logic Puzzle

#71

Post by vytasgd »

MereInterest wrote: post #64
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…

If n=3, then each of the blue-eyed people know that there are blue-eyed people and know that the other blue-eyed people know. However, they don't know that all the blue-eyed people know that the blue-eyed people know. This is the piece of information that is learned by the statement given. In general, if there are N blue-eyed people, then it is the Nth abstraction of "he knows that I know that he knows that I know th…

Can you go into further detail about the nth abstraction of "he knows that I know..." and what effect that has on the population? The way I see it is that as soon as everybody knows that there are blue-eyed ppl and everybody knows that everybody else knows there are blue-eyed ppl the countdown begins... additionally, at that point you can already get to an infinite number of abstractions of the "he knows that I know that he.." statement because you both know that the other knows blue-eyed ppl exist, so you both know that the other knows that you know that blue-eyed ppl exist, so you both know....

Re: Blue Eyes Logic Puzzle

#72

Post by Mindless2112 »

MereInterest wrote: post #64
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…

If n=3, then each of the blue-eyed people know that there are blue-eyed people and know that the other blue-eyed people know. However, they don't know that all the blue-eyed people know that the blue-eyed people know. This is the piece of information that is learned by the statement given. In general, if there are N blue-eyed people, then it is the Nth abstraction of "he knows that I know that he knows that I know th…

At n = 3, every blue-eyed person knows everything every other blue-eyed person knows and that every blue-eyed person knows it, so you can already construct an infinitely-long chain of "I know that he knows that I know that he knows..." at that point.

(Of course, I am assuming that all the people think/reason exactly the same and that they all know that they think/reason exactly the same, which are assumptions of the original problem.)

Re: Blue Eyes Logic Puzzle

#73

Post by anonymoushn »

Smaug123 wrote: post #33

There's an infuriating variant, which I have as yet been unable to solve: An infinite sequence of people have either blue or brown eyes. They must shout out a guess as to their own colour of eyes, simultaneously. Is there a way for them to do it so that only finitely many of them guess incorrectly?

And none of them have any knowledge about anything?

Re: Blue Eyes Logic Puzzle

#74

Post by dllthomas »

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…

Also, you need "everyone knew on day X that..."

Re: Blue Eyes Logic Puzzle

#75

Post by Mindless2112 »

DannoHung wrote: post #66
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 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.

Re: Blue Eyes Logic Puzzle

#76

Post by Smaug123 »

anonymoushn wrote: post #73
Smaug123 wrote: post #33

There's an infuriating variant, which I have as yet been unable to solve: An infinite sequence of people have either blue or brown eyes. They must shout out a guess as to their own colour of eyes, simultaneously. Is there a way for them to do it so that only finitely many of them guess incorrectly?

And none of them have any knowledge about anything?

They can all see everyone else's eyes. That is, person N can see person M's eyes, for all M,N. [I don't know whether it's possible or not - it feels not, but it has been hinted to me that it is possible.]

Re: Blue Eyes Logic Puzzle

#77

Post by dllthomas »

Mindless2112 wrote: post #17
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.

It's not so much that the statement was ambiguous or wrong -- it's that the statement gave no one in the tribe more information than was previously available to him/her. Everyone in the tribe already observes at least 99 members with blue eyes, and everyone knows that everyone else observes at least 99 members with blue eyes, so the statement should have no effect. Edit: split to separate comment.

But they don't know "everyone knew on day X" so there is ambiguity about when they would be counting from, so nothing can be deduced. The foreigner's statement provides a synchronization point: clearly everyone knew at that point.

Re: Blue Eyes Logic Puzzle

#78

Post by pavelrub »

Smaug123 wrote: post #33

There's an infuriating variant, which I have as yet been unable to solve: An infinite sequence of people have either blue or brown eyes. They must shout out a guess as to their own colour of eyes, simultaneously. Is there a way for them to do it so that only finitely many of them guess incorrectly?

This is not a variant of the puzzle above.

This is a variant of the hat puzzle, and the solution requires some set-theory.

Re: Blue Eyes Logic Puzzle

#79

Post by axus »

jwpeddle wrote: post #63
axus wrote: post #58

Earlier quoted context omitted.

The time which everyone made an accurate count was the new common knowledge. I believe the traveler's words added no new information, or even his presence (other than bringing everyone together). It was the gathering together, where everyone could see everyone else, and know that counts were synchronized. I think if there were an earlier all-hands-meeting without the traveler, the counts would have been synchronized…

Not sure what you're refering to by "count" here. There's nothing to count. What matters is everybody coming into the knowledge that everybody knows at least one person has blue eyes. This takes a prompt about that, which is the foreigner's speech. If the foreigner doesn't cause them to start sorting themselves into blue eyes/not blue eyes groups, there's no basis for them to start deducing anything.

Counting is how they measure the days passed versus how many blue-eyed people they see. I'm sure you're right, but I have to check the assumption that seeing everyone is the same as hearing a fact about everyone.

Re: Blue Eyes Logic Puzzle

#80

Post by vytasgd »

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…

I've been with you on this, but I think we are wrong. Here's where I'm at: (without foreigner's statement)

1 blue eyed person- He know's nothing, nothing happens

2 blue eyed people- Each thinks the other could be the only blue but they don't know it... deadlock.

3 blue eyed people- Each thinks the other two are caught in the 2 person deadlock scenario knowing nothing.

4 blue eyed people- Each thinks the other 3 are caught in the 3 person scenario etc...

Once the foreigner adds the knowledge:

1- he'd leave the first day

2- the second would recognize the first didn't leave, they'd both leave on day 2

3- the third would recognize the first two didn't leave on day 2, etc, etc, we were wrong...bollocks.

Post reply on HN