Problem in Logic

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of her eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not indicate her own eye color; as far as she knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and she could have red eyes.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves ever."

Here is your one and only hint. Don't read this unless you have thought about the problem for a few days, and you just aren't getting anywhere.

Mathematicians have learned to solve a hard problem by reducing it to a simpler one, and then ratcheting up. To be fair, sometimes we have to do the opposite. Sometimes a problem seems easy, but we just can't solve it, and it is in fact easier to solve a more general version of the problem, and then apply it to the specific case that confronts us. But that is very rare! Most of the time you want to solve an easier version of the problem first, and then work up. So with this in mind, solve the same problem with one blue-eyed person, one brown-eyed person, and the guru. Who leaves, and on what night?

Here is the solution. If we consider an island with 1 blue-eyed, 1 brown-eyed, and the guru and she says her line, the blue-eyed would leave at midnight. She knows the guru is talking about her.

It is important to note that it makes no difference how many brown-eyed people are on the island. There could be zero, there could be a million. If Sally is the only one with blue eyes, and the guru says she sees blue eyes, it has to be Sally, and off she goes that night.

If we consider an island with 2 blue-eyed, 2 brown-eyed, and the guru and she says her line, Sally would say, "Suppose I don't have blue eyes. Jane does, I can see that. So if my eyes are any other color, then Jane will figure out she has blue eyes, and she will be taken off the island tonight." The next morning, when Jane is still there, Sally knows she has blue eyes.

The great part about this is that we don't have to do this for each blue-eyed person. Sally and Jane are mathematically equivalent, i.e. they are in exactly the same situation. So they both fly off on the second night. Again, it doesn't matter if there are 0 brown-eyed people, or two, or a million; or 7 red-eyed people, etc. You only need two blue-eyed people on the island for this to work.

Now for the inductive step. Sally says, "Suppose my eyes are not blue. I count n-1 people with blue eyes, and they all think like me, so if my eyes are not blue, they will all fly away on night n-1." After this does not happen, Sally, and all the other blue-eyed girls, leave the island on night n.

And yet, this seems to be a paradox. Surely the Guru has given us no new information. She told us someone has blue eyes - we can clearly see that. So for extra credit, what new information is the guru providing? I'm not sure I have a satisfactory answer to this one myself.