A group of girls 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 girls, 100 brown eyed girls, and the Guru (she happens to have green eyes). So any given blue eyed girl 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 couple 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 girl, one brown eyed girl, 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 perform this analysis for each blue eyed girl individually. 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?
Perhaps the guru imparts a theory of mind. Sally knows Jane has blue eyes, but after the guru speaks, Sally knows that Jane knows that someone has blue eyes. This makes sense to me, but if you try to ratchet it up to n blue eyed girls, your brain will ache.
For even more extra credit, prove that n girls cannot leave before night n. They can leave on night n, as shown above, but they cannot leave any sooner. This is technically part of the problem, though it is a detail that many people overlook. It is fairly intuitive, but not easy to prove.
The trick is to use induction on the number of nights, rather than the number of blue eyed girls. On night 1, 1 blue eyed girl can leave, but more than one must stay. On night 2, 2 such girls can leave, more than 2 must stay. Proceed by induction on n. For i in 1 to n-2, i girls can leave on night i and no more. Thus n-2 girls can leave on night n-2, and no more. Step up to night n-1, remembering that n-1 girls can indeed leave on night n-1.
Suppose Sally is one of n blue eyed girls, or perhaps more than n blue eyed girls. The n-1 girls she sees around her (perhaps more than n-1 girls), cannot leave prior to night n-1. Sally knows this. Prior to midnight of night n-1, the girls around her stay, whether her eyes are blue or brown. Her eyes could be blue, or brown, and everything up to night n-1 would be the same. She doesn't have enough information to decide. She, and the other girls, cannot leave on night n-1. n or more girls must stay, at least to night n. Turn this around, and on night n-1, n-1 girls can leave, and no more. That is the inductive step. Switching back to girls, for each n, n girls can leave on night n, and no sooner.
This is an example of an induction puzzle, so named because induction is at the heart of the solution. I like this puzzle because it has a synchronizing event, the fairy who comes at midnight. The next example, the 3 hats problem, has no CPU clock, and that raises a new set of questions.
Here is the 3 hats problem. The king had three prisoners, but on a lark he decided to let one of them go. He placed a hat on each of their heads, so that each prisoner could see the other two hats, but not his own. Each hat was either red or blue. The king told the prisoners that at least one of them was wearing a blue hat, and whoever deduced the color of his hat would be released. A prisoner who guessed wrong would be killed on the spot. The prisoners could not speak to each other, nor gesture etc.
The prisoners sat for a few minutes, then one of them stood up, announced his color, and was released. What did he say, and how did he work it out?
Here is the solution. It is really the same as the blue eyed girls problem above; just think of the red hats as brown, and the numbers below as successive nights.
If there is just one blue hat, the person with that hat would see two red hats, and since the king specified that there is at least one blue hat, that prisoner would immediately know the color of his hat. This did not happen, hence there is more than one blue hat.
If there are precisely two blue hats, each prisoner with a blue hat would see one blue and one red hat. Since they have already realized that there must be at least two blue hats, both of these men would know that he was wearing a blue hat. This does not take place, hence all three hats are blue.
Since there are three blue hats, the first man to figure it out stands up and says “Blue”.
You might think there is no need for step 1, since each prisoner sees two blue hats from the get-go. However, Sam, who is eventually released, doesn't know his hat is blue at the outset. He looks at Bill, who doesn't know his hat is blue either. As far as Sam is concerned, Bill might see a blue hat and a red hat, and Bill must consider the possibility that his hat is red too, leaving only one blue hat. Sam must know, that Bill knows, that John, with perhaps the only blue hat, has traveled down this path and said nothing. Thus Bill knows there are at least two blue hats, and still says nothing. Each prisoner must move through all three steps as outlined above.
The solution troubles me, because there is no CPU clock. In the previous problem, with the girls on the island, they make there inferences in parallel, as though they were all thinking as one; then something happens at midnight that tells each girl if any of the others have drawn any conclusions. Logic circuits click along, step by step, like digital circuitry on a motherboard. But this problem, the 3 hat problem, has no clock. How quickly does each man think? Not at the same speed obviously, because one of them stands up first. But if they don't think at the same speed, how can anyone know when the others have reached a logical conclusion? The solution says, “after a few minutes”. What does that mean? It seems to me the correct answer would assert nobody figures out his own color, because he can't be sure how quickly the other men think, or they all stand up at once, because they all think at the same speed.
Perhaps we are to assume the men think at a speed that is distributed randomly about a mean, in a normal distribution. The three men's brains have to be close to the mean for this to work. After a time, which is precalculated to optimize success, the faster thinker, i.e. the smarter man, will assume that enough time has gone by for the slower prisoners to make the first two deductions, with the caveat that they have not yet had enough time to make the last one. Sam makes the last deduction, stands up, announces his color, and is released. This means he must know about the average speed of thought, and the distribution about the mean. He waits long enough so that it is likely that the others have taken the first 2 steps along the path to the solution, whence he can make his final proclamation. He could wait longer of course, and the longer he waits, the more certain he is of his color; but the longer he waits the more he risks losing the game, because another prisoner solves the puzzle first. He chooses his time interval carefully, to optimize the probability that the other prisoners have taken the first steps in logic, but not the last. It has become an exercise in continuous game theory.
It's funny how the solution makes sense to us at first. We naturally make assumptions about intelligence, and thought, and the speed of thought, and variations among individuals, and the distribution of these variations clustering about a mean. We fill in all the details based on our life experience, the kid in class who was a bit faster than us, or a bit slower, and then the solution makes sense. But upon further reflection those details are troubling, at least to me. They are certainly omitted from the problem description. And so I prefer induction puzzles with some form of CPU clock, as illustrated by the blue eyed girls problem above.
The way to fix this problem is to have the king ring a bell, at which point each prisoner stands up and announces his color, if he knows it. The bell is like the synchronizing clock, like the fairy who comes at midnight. Each bell tells each prisoner that the others have or have not reached a conclusion. Each bell causes each prisoner to advance in his logic, and at the third bell all three prisoners stand up and shout “Blue”. Of course real world problems in relationships, business, geopolitics, and other social interactions do not have a synchronizing clock, so perhaps the original 3 hats problem, as stated, is more realistic. Our theory of mind naturally includes assumptions about intelligence, and the speed at which another person can make an inference.