Crazy Questions at Google Job Interview

It took me a long time to articulate what new information was being given; much longer than answering the question itself. The trick is to imagine a smaller scale. Lets say there were three each of brown- and blue-eyed people. And let's call the blue-eyed people 1, 2, and 3. Everyone knows that everyone sees at least one blue-eyed person, so no new information, right?

Look at this fact: before the announcement, 1 doesn't know if 2 knows if 3 sees a blue-eyed person. (2 knows if 3 sees a blue-eyed person, because 2 knows that 1 has blue eyes, but 1 doesn't know any of that.)

Then, after the announcement, the first night passes and 3 doesn't go home -- so now 1 knows that 2 knows that 3 sees a blue-eyed person. That's the new knowledge.

To finish the riddle, now 1 can reason like this: if my eyes are brown, then 2 knows her eyes are blue, because 2 knows 3 sees a blue-eyed person. (That's the new knowledge.) So if 2 goes home, my eyes are brown. And if my eyes are blue, then 2 will know that 3 sees a blue-eyed person that isn't me, and 2 won't go home. Either way, 1 goes home the 3rd night. And 2 and 3 are actually in the same position, and they go home too.

(It seems like the brown-eyed people go home the next night, but I forget and am too lazy to think about it rigorously again.)

If you want to analyze this for n=4, start with this fact: 1 doesn't know if 2 knows if 3 knows if 4 sees a blue-eyed person. Don't try this if you're sleepy.