No, you need a guru or outsider to make the statement.
Here’s one I tried to complexify based on a simpler puzzle.
I used to work at Snapple. Let me tell you how I got to be manager of the bottling plant.
Back then, we made two types of tea: sweet and unsweet. We sold the bottles in three types of pallets: sweet, unsweet, and assorted (50 of each). 100 bottles per pallet.
My first day, I was a delivery driver, and I had one of each type of pallet, all labeled and ready to go. Just as I was leaving, though, my boss got a call from the bottling plant manager. “Uh, we got a problem,” he said. “I just noticed that the machine that labels bottles was broken, and none of those bottles are labeled.”
My boss groaned. “Fine. We’ll send them back. Label the sweet, label the unsweet, and throw out the assorted, because we can’t figure out what labels to put on those.”
“Uh, we got another problem,” the bottling manager said. “I remember noticing that the guy who labels the pallets put the wrong label on each pallet.”
“You’re kidding. Okay, which label did he put on which pallet?”
“Uh, I forget?”
My boss hung up and turned to me. “First thing we do is, we fire that guy. That guy’s terrible. But now we got a huge mess: how’re we gonna figure out which pallet is which? We gotta start opening and sampling bottles of tea until we find a sweet and an unsweet in the same pallet, and who knows how many bottles of tea we’ll ruin before we figure that out?” He explained the whole situation to me.
“Look,” I said. “I think I can solve this whole thing super-quickly. If it takes 15 seconds to move a label from one pallet to another, and 10 seconds to sample a bottle, I’ll get every pallet labeled in less than a minute.”
“You do that,” my boss said, “and you’re getting a promotion.”
What did I do?
Bonus question: I told my boss how to salvage the assorted tea. What did I tell him?
My solution:[spoiler]You went to the pallet marked Assorted. You know it isn’t really Assorted so it’s either Sweet or Unsweetened. You sample a bottle to find out which it is.
Say for the sake of argument that it’s Sweet. You now know that the pallet marked Unsweetened must be Assorted; it can’t be Unsweetened because it has the wrong label and it can’t be Sweet because you’ve identified the Sweet pallet. You now know the remaining pallet, which is marked Sweet, is actually Unsweetened because that’s the only possibility remaining.[/spoiler]
My solution:You dump all the assorted tea back into the bottling tank. Being a mix of half sweet tea and half unsweetened tea, it has half the normal amount of sugar that sweet tea has. So you add another half measure of sugar to the batch. It’s now regular sweet tea and you can bottle it and sell it.
Why?
We have to assume that the islanders know no more than we do. They don’t know when the rules went into effect, they don’t remember how they got there, all they know is what is expressed in the riddle. Since they can’t communicate they can’t coordinate, none of them knows what the other knows. So it takes the guru to say something so that they all have to start their reasoning from the same day.
I have a solution to the blue-eyes puzzle, but since people are saying that the presence & statement of the guru are important, I’m probably wrong. My answer would be:
At midnight, it’s dark. I go to the boat and say, “My eyes (irises) are currently black. I’d like to leave now.”
The guru transmits a special kind of knowledge called common knowledge. Common knowledge means not just that “everyone knows X”, but that “everyone knows that everyone knows X”, “everyone knows that everyone knows that everyone knows X”, and so on infinitely. It’s not knowledge that any islander could have already had, because they can’t observe themselves.
Take the case of three islanders. I can see two people with blue eyes. I know that everyone can see at least one person with blue eyes, because the two others can obviously see each other. But I don’t know that everyone knows that everyone can see someone with blue eyes. If, hypothetically, I had brown eyes, then one of the other people (B) can’t know that the third person (C) sees at least one person with blue eyes, since B can’t know that he has blue eyes. So we have an “everyone knows X” but not an “everyone knows that everyone knows X”. The guru gives us this knowledge no matter how many people there are.
Mine is the same as yours in every respect, except for the second part my suggestion was to create a new “half and half” or “diet” version by mixing the assorted bottles together in one big vat and rebottling them. But this would involve new labels, branding etc so your version is much better.
Maybe I’m not seeing what you’re saying, but this doesn’t seem to address my point.
Anyone on the island could imagine a truth-telling guru who could say “I see a blue-eyed person” because everyone on the island can see a blue eyed person. So it isn’t necessary for the guru to actually exist and make the statement.
Their inability to observe themselves is irrelevant. The point is that everyone on the island can see a blue eyed person. So they already know that a guru could make the statement that she sees a blue eyed person. The actual statement would add no new information.
If three people were on the island, the guru’s statement would be adding new information that not everyone on the island would have had before the statement. But we’re not addressing the case of their being three people on the island.
New information is added no matter how many people are there. It’s just that the order of information changes (order in the sense of first order, second order, etc.).
It’s utterly crucial that the guru make the announcement publicly. That’s the only way the statement can become common knowledge. Suppose the guru interviewed each islander privately: he says to me that there’s at least one blue-eyed person on the island. I say that’s fine, but I need to know that he’s told everyone else this information. He says yes. But wait, that’s not good enough: I need to know not just that everyone heard this, but that everyone knows that everyone heard this. The guru again replies yes. That’s still not good enough, though: I need to know that everyone heard this last bit of information as well. And so on, infinitely.
A public announcement solves this problem. I can see that everyone heard the announcement, and that they can see that I heard it. So we all have the knowledge to whatever “everyone knows that everyone knows” level that is necessary.
On the eye colors: You know what you know. You have some, but not full, information on what anyone else knows. You have even less information on how much they know about what anyone else knows, and so on. And somewhere, n layers deep, the guru does actually add new information.
If you’re mathematically inclined, you can prove the result using mathematical induction.
Another one I’m fond of is the old “nine dots, four lines” puzzle, with a twist (which sometimes shows up accidentally). Something like this:
Nine dots are arranged in a square, thus:
O O O
O O O
O O O
Using only straight lines, and without removing your pen from the paper, draw lines through all of the dots using the fewest number of lines possible.
The answer isn’t what you think.
EDIT:
Well, not quite infinitely. Finite-order knowledge would be sufficient for this problem (though still short of true public knowledge), though it would have to be a fairly high finite order.
Hey Biotop, if you’ve got a family full of puzzle-lovers, this is the only thing you need:
The cover is goofy looking, but the puzzles and challenges are serious. Highly recommended.
True. I probably should have said that you need arbitrarily-high order knowledge for an arbitrarily large number of villagers. The guru provides infinite-order knowledge and so solves the problem no matter what the N.
It looks like the dots are of non-zero size :). I hope the paper is big.
Those are my solutions in every respect–excellent! These may be too easy for Biotop’s family, alas :).
You land on an island with two tribes (completely different in appearance.)
The ‘Honest’ lot always tell the truth and the ‘Fibbers’ always lie.
You come to a fork in the road (you know that one way leads to the village you want to visit and the other way leads to a swamp) and meet two natives - one of each tribe. Can you ask just one question to find the village?
'Ask either native “If I asked the other native the way to the village, what would he say?” In either case, take the path they don’t indicate.
You land on an island with three tribes (completely different in appearance.)
The ‘Honest’ lot always tell the truth, the ‘Ditherers’ either lie or not at random :eek: and the ‘Fibbers’ always lie.
You come to a fork in the road (you know that one way leads to the village you want to visit and the other way leads to a swamp) and meet three natives - one of each tribe. Can you ask just one question to find the village?
'Ask any native “Did you know they are serving free beer in the village?” Then follow all three natives! 
Cute, though there is a solution. It’s a bit of a cheat, though:[spoiler]“If, instead of this question, I had asked ‘Which way to the village?’, what would your answer have been?” Note that this only works if the ditherer always tells the truth/lies consistently within a question, even when there are embedded hypotheticals.
At least the third guy doesn’t stab people that ask tricky questions :).[/spoiler]
The Blue Eyes solution
Khan Academy has a similar enigma with blue foreheads. The instructor explains the setup in the first video. He recaps it in the second video for the first 3 minutes then explains the solution.
Mainly, it involves a lot of “if/then” statements, then using a pattern to determine the solution. I have to write it down step by step to understand the solution myself. There’s no way to condense it.
[spoiler]
Start with imagining that there’s just one person aside from the guru. The rule is that once the person realizes his eye color, he gets to leave that night.
The guru says “I can see someone who has blue eyes.” That one person realizes it’s him, so he leaves the first night.
Now imagine there’s two people. Neither knows their own eye color, but can see the color of the other’s eyes. The guru says “I can see someone who has blue eyes.”
If number 1 sees that number 2 has brown eyes, he realizes he must have blue eyes, since he’s the only other person, so he gets to leave that night.
If number 1 sees that number 2 has blue eyes, he still doesn’t know what color his are. He’ll wait to see what number 2 does. If number 2 sees that number 1 has brown eyes, he’ll leave that night. If number 2 stays, that means that number 1 has blue eyes. Both leave on the second night.
Now imagine the island has three people.
The possible eye combinations are:
3 blues
2 blues, 1 brown
1 blue, 2 browns
3 browns — not possible because the guru says “I can see someone who has blue eyes.”
Nobody sees
Number 1 could see:
A-the other two have brown eyes
B-one has blue eyes, the other has brown eyes
C-the other two have blue eyes
Situation X: If number 1 sees two brown-eyed people, he would realize he has blue eyes, because at least one person has blue eyes. He gets to leave the first night.
Situation Y: If number 1 sees one blue-eyed person and one brown-eyed person, he doesn’t immediately known his eye color, so he doesn’t leave the first night. He waits to see if one of the others will leave. If the blue-eyed person leaves, that means number 1’s eyes must be brown, since the blue-eyed person sees case A. Number 1 gets to leave the second night. If the blue-eyed person doesn’t leave, that means he doesn’t see case A. There’s no case C for blue-eyes to see, so number 1 knows blue-eyes sees a case B. Therefore number 1 realizes his eyes aren’t brown and leaves the third night.
Situation Z: If number 1 sees two blue-eyed people, he doesn’t immediately known his eye color, so he doesn’t leave the first night. He waits to see if one of the others reacts to seeing one blue-eyes and one brown-eyes and acts out Situation Y. If they don’t, they don’t leave the second night. Number 1 therefore must have blue eyes and gets to leave on the third night. The others draw the same conclusion and leave on the third night as well.
This is as far as I’ve gotten. I don’t think I can explain a 4-person situation. Extrapolate from there or just let Khan Academy sum it up for you in the linked videos.[/spoiler]
You either recognize that there is a pattern, and accept that it will hold for an arbitrary number without writing it out, or you formalize that with a mathematical induction setup. Trying to actually write out the n=100 case is insanity.