Blue Eyes - A Logic Puzzle (spoiler in the comments) | Hacker News Reader

Blue Eyes - A Logic Puzzle (spoiler in the comments)

xkcd.com

3 pointspalish7 comments

I wrote about what information the guru gives recently:

http://news.ycombinator.com/item?id=56196

Normally I don't cross-post, but this was too interesting. Solution is here: http://xkcd.com/solution.html

[Edit: this was originally garbled in rot13 with a warning of SPOILER ALERT. I have decoded it back to readable text since the spoiler warning has been added to the post title.]

From the solution page:

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

Indeed! I can understand the solution, but I don't know how the word of the Guru matters. Rather, under the given rules, everyone should leave the island exactly on the 100th midnight after the 'game' starts. Say, after they enter the island, or after the rules are established.

While amusing, the point of posting this to News.YC is to openly discuss the solution :P

Upmodded for geekiness anyway though.

From what I understand, it's the fact that everyone knows that everyone else knows that someone has blue eyes that matters. You have to look at it with an extra layer of indirection.

Yes, but they don't need the guru to tell them that, do they? Do you mean the green eye guru thing is just red herring?

[Edit:] Besides, I claim the solution is wrong. Everyone but the guru needs to leave on the 100th midnight. Everyone but the guru sees one group of 99, so everyone should know to wait 99 days, then conclude that if the other folks in that group haven't left it's because they see a group of 99 too.

The guru doesn't leave because he sees two groups of 100, so he will wait 101 days. By that time, everyone has left, which means there were indeed two groups of 100 and herself had a different color.

Note that everyone but the guru sees a group of 1 (the guru), but this does not mean that everyone must leave at day two unless the guru has left the first day. That's because the guru doesn't know there is anyone with green eyes. If he knew, he'd trivially conclude it had to be him, so he had to leave the first day. None of this affects the other 200 at all.

[Edit^2:] I don't really believe I'm right; I just fail to see what I'm missing. I realise that the guru is there to somehow kickstart the induction providing the base case, and that the previous paragraph somehow has the key to this. But I fail to grasp how that is really necessary.

[Edit^3:] OK, it goes like this. We have to prove the thesis that if I see any group of n people with the same eye color, I can NOT conclude that I belong to that group, after any number of days, until someone publicly reveals that there is at least one person in that group.

The paragraph right before Edit^2 explains the base case of a group of one. Now we have to establish the induction step: if the thesis is true for a group of n, does it necessarily follow for n+1? Yes, because if I am not in the group, each person in the n+1 group only sees n other people with the same eye color. Which, by the induction hypothesis (i.e., that the thesis is true for a group of n), doesn't let them conclude anything, after any number of days. Therefore, I can't infer anything from their failure to leave the island after any number of days.

Makes sense?

"Everyone but the guru sees one group of 99"

No, the guru and the people with brown eyes see 100 people with blue eyes.

Edit: I see now that you really meant "a group of 99", not "99 blue-eyed people". My comment doesn't apply. FWIW, I don't think it matters how many brown-eyed people there are.

Yes, I meant "a group of 99 people with the same color"; sorry for not making it clear. And I see now that brown-eyed people don't matter, but the reason why they don't matter turned out more involved than I originally thought.

Reply on news.ycombinator.com