Thread: The hardest logic puzzle in the world

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 their eyes. Every night at midnight, a ferry stops at the island. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight. 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 tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he 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, nothing dumb. 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."

*I will post the answer in a few days*

Basically, there are people who are color BLIND, meaning they don't see certain shades of red or green or blue, even though the color of their eyes to the observor may betray that fact.

We really need to define what a color is, as a subject-object thing....or maybe we should stick with black and whites.

Dualities.

Just so as not to be boistrous.

I agree.

You have 48hours.

Everyone with blue eyes? Also that night.

wrong!

Also, if you think you have the answer, please provide the logic of it.

I would, but I'm lazy. Usually logic "puzzles" have some bullshit answer that only serves to piss everyone off by being "just logical enough" to slip by.

Believe me, the answer to this is extremely logical but VERY complicated! I dont know anyone who has actually got the right answer without being told.

But there isn't an annoying tricksy answer. It can be proved by mathematical induction.

Ermm... I googled it ... I would NEVER think of that...

:? Yeah that is one way to approach the issue

I hope g07g6008 will forgive me for providing everyone else with a clue:

The key to figuring this out is to remember that not only is everyone on the island a perfect logician, but also that everyone knows that everyone else is also a perfect logician.

I googled it too, but didnt really understand it even after I first read the explanation. I think in sunk in after a while, though.

I do forgive you.

In fact, tomorrow I will put up the answer without an explanation and give everyone a day to try and come up with the logic behind it. This is still quite difficult, believe me.

I'd rather not entirely ruin it, so let me suggest my solution and a method of proof. All blue-eyed people leave on the 100th night, and nobody else leaves. In general, if there were n blue-eyed people, they would all leave on the nth night, and nobody else would leave. This is trivial for n = 1. To show it in general, proceed by induction.

Here's the part that I'm having trouble with. When n>1, the guru is not really telling anybody anything they do not already know. On one web site, somebody said the guru just provides a starting point for all the perfect logicians to start their calculations. But, how come they didn't already start their calculations before the guru spoke? If everybody knows, and knows everybody else knows, why wasn't there a point in time when that condition first existed, that would have started the sequence already? I'm thinking the guru might be a red herring in the logic problem.

It's kinda like a trigger. In the case of n=1, without the guru he would never know there is someone with blue. But when the guru says there is at least 1 person with blue he know. I guess just extrapolate from there... maybe?

Originally Posted by shawngoldw

It's kinda like a trigger. In the case of n=1, without the guru he would never know there is someone with blue. But when the guru says there is at least 1 person with blue he know. I guess just extrapolate from there... maybe?

But there are 100 people with blue. Even every blue can see 99 other blues without the guru telling them.

As I thought, this isn't too logical at all. If they were perfect logicians (a fallacy/paradox in itself), then they would be capable of figuring it out beforehand. Perfection, you see. Kind of like omniscience.

The answer, although I haven't looked it up, will probably be highly unsatisfactory. I hate "logical" puzzles because they normally follow this line. They begin with a paradox, and end assuming the paradox was solved (hint: It wasn't).

Originally Posted by GhostofMaxwell

But there are 100 people with blue. Even every blue can see 99 other blues without the guru telling them.

But they don't know there are 100 blues. From what they know there may only be 99 blues. They can be ANY color. But when the Guru says someone has blue they start trying to figure out if they have blue. If the guru said someone has turquois they would try to figure out if they had turquois

But how is the guru telling them any more than they can already see?

I just thought of something. If everyone (this includes the guru) is a perfect logician, why did she/he make the illogical choice and say "I see someone with blue eyes" instead of naming off how many of each eye color there was.

That, in effect, would have solved it in a...dare I say...MORE LOGICAL MANNER?

Originally Posted by GhostofMaxwell

But how is the guru telling them any more than they can already see?

I have no idea, but maybe if we knew the math we could see?

Originally Posted by jeremyhfft

I just thought of something. If everyone (this includes the guru) is a perfect logician, why did she/he make the illogical choice and say "I see someone with blue eyes" instead of naming off how many of each eye color there was.

That, in effect, would have solved it in a...dare I say...MORE LOGICAL MANNER?

Who ever said the Guru was trying to get everyone off the island? 8)

The most logical choice would be to get everyone off the island. Perfect logicians and all. The next logical choice, would be to decide that your own eyes were green, simply by deductive reasoning regarding how the "rules" work.

It's flawed. End of story.

Ok, for those of you who dabble in mathematics, you will understand that a riddle of this nature is just an english interpretation of an interesting mathematical concept. The point of the exercise is not to scrutinize the concept but to solve the puzzle given its constraints.

All logic problems of this form which can be solved by mathematical induction require a "Basis Step" which is the initial "push" so to speak from the guru. This is needed for the proof to continue otherwise it would not be mathematically correct.

I will post the answer in a few hours and then the explanation tomorrow.

Here is the answer: :P

100 blue-eyed people leave on the 100th night

I will post the explanation tomorrow...
In the meanwhile, someone come up with their own one

Bull fucking shit

:? ?

you're just making shit up as you go along.

I'm not. There is a plausible explanation which I will post tomorrow, you'll see...

From the first premise this is ridiculous.

OK, you seem to be itching to be proved wrong so here goes:

Lets give a general constraint and say that there are n number of people with blue eyes...

When n=1, that person knows it must be him as he sees no-one else with blue eyes. He leaves on the first night.

When n=2, each of the two blue eyed people see only one other person with blue eyes but, for all they know, that one person could be the only one with blue eyes. The other person sees the same thing. BUT, when after the first night neither of them have left, each one deduces that the other must be seeing someone else with blue eyes and, since there is no-one else to be seen, that person must be them. They both leave on the second night.

When n=3, each person sees two others with blue eyes and expects them to leave on the second night, for he (being a perfect logician) has already considered the previous possibility. When after the second night, no-one leaves, he realizes that he must have blue eyes too. Three people leave on the third night.

And so it goes on... All 100 blue-eyed people count 99 others and know that if, on the 99th night, no-one leaves then they must have blue eyes.

There it is. According to me this really is the hardest riddle I have ever heard!

Here is the next one. This riddle was also claimed to be the hardest in the world!

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.


Here are some clarifications:

* It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).

* What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)

* Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

* Random will answer 'da' or 'ja' when asked any yes-no question.

This is the dumbest version of "knights and knaves" I've ever heard. Good god. Just give it up. Please.

Originally Posted by g07g6008

Ok, for those of you who dabble in mathematics, you will understand that a riddle of this nature is just an english interpretation of an interesting mathematical concept. The point of the exercise is not to scrutinize the concept but to solve the puzzle given its constraints.

All logic problems of this form which can be solved by mathematical induction require a "Basis Step" which is the initial "push" so to speak from the guru. This is needed for the proof to continue otherwise it would not be mathematically correct.

I will post the answer in a few hours and then the explanation tomorrow.

I disagree. The statement of a logic problem should be logically airtight. As of right now and until I hear a better explanation, I see no reason why the perfect logicians would start their calculations just because somebody told them what they already knew. A fairer statement of the problem would be if the king of the island suddenly decreed the rule about the eye colors. This would give people a better chance at solving the problem, instead of having their minds boggled over an impossible situation.

Lets give a general constraint and say that there are n number of people with blue eyes...

When n=1, that person knows it must be him as he sees no-one else with blue eyes. He leaves on the first night.

When n=2, each of the two blue eyed people see only one other person with blue eyes but, for all they know, that one person could be the only one with blue eyes. The other person sees the same thing. BUT, when after the first night neither of them have left, each one deduces that the other must be seeing someone else with blue eyes and, since there is no-one else to be seen, that person must be them. They both leave on the second night.

When n=3, each person sees two others with blue eyes and expects them to leave on the second night, for he (being a perfect logician) has already considered the previous possibility. When after the second night, no-one leaves, he realizes that he must have blue eyes too. Three people leave on the third night.

And so it goes on... All 100 blue-eyed people count 99 others and know that if, on the 99th night, no-one leaves then they must have blue eyes.

....But no one can leave on Xn nights regardless! No one knows they have blue eyes themselves, and the riddle sets no other condition for leaving.

How is the guru initiating anything? Or is his saying he sees a person with blue eye irrelevant?

Let me pose a riddle similar to the blue eyes problem which does away with the dilemma of people seeing blue eyes before the guru announces that blue eyes exist. It's a superficial difference, as the problem still relies on the distinction between personal knowledge and common knowledge (which is why the guru's statement does "pull a trigger"), but it should appease those of you who are at least willing to accept a wacky premise for a logic problem. (And those of you who can't suspend disbelief for two seconds so as to have a little bit of fun... lighten up!)

On another island there exists a population of 200 exotic birds. These birds, like the people on that other island, are pretty good at logic and have no way of communicating with each other (probably due to lack of predators on the island... they just amble around and eat magical gumdrops that fall from the sky). Each bird has a single magnificent feather atop its head. Should the magnificent feather fall off its head, and should the bird realize one day that this has happened, the bird will die that night of abject misery. One night, while the birds are sleeping and dreaming of blue diamonds and purple horseshoes, 100 of them lose their magnificent feathers. All but one of them blow away into the ocean. In the morning, as the birds arise, they all notice that a number of their friends have lost their magnificent feathers, and they all take note of the lone magnificent feather lying on the beach. Which birds, if any, die, and when do they die?

The 100 that still have their feather.

Because they get stressed out not knowing if the solitary feather belongs to themselves, as a result the 100 actually see their feather fall in front of their eyes.

Originally Posted by serpicojr

Which birds, if any, die, and when do they die?

N=1. Bird A lost the feather, knows it is his, dies immediately
N=2. Bird A lost a feather, sees bird B w/o feather, Bird B des not die 1st night, they both die next night.
N=3. Bird A lost a feather, sees B and C w/o feather, B and C do not die second night, all three die third night. Etc. So it is really the same logic problem and they die on the 100th night.

Does the same thing happen if all 100 feathers blow into the ocean?

No it doesn't, the birds get to spend their lives dreaming of blue diamonds and eating magic gumdrops.

The trick here is you need something to start off the induction, that key n=1 step requires a guru/single feather etc.

I've always known this problem as the cheating husbands problem btw.

Hmm. I'm still not happy with this. With multiple feathers lost, all birds know multiple feathers were lost, whether or not one is seen on the beach. So what does the feather really do?

Ok, assume you have only one bird which has lost its feather - without seeing the feather on the beach how would it know it was featherless? Remember that the birds know that the other birds are featherless but has no reason to think that it has lost its feather until it spots one on the ground.

This case is the one that allows you to argue for the other 99 birds.

Suppose I am one of the birds. Aside from a lone featherless bird, any bird I can imagine must consider that there is some bird which sees one fewer featherless bird that it does--namely, if that bird assumes that it didn't lose a feather, then any featherless bird it sees must see one fewer featherless bird. So I must consider a bird that sees one fewer feather than I do. But then that bird must consider a bird which sees two fewer feathers than I do. Now I have to take that hypothetical bird into account, so I must consider a bird which sees two fewer feathers than I do. I know such a bird does not exist, but its possible that some bird I am considering does accept this possibility. But then this bird can imagine a bird which sees three fewer feathers than I do, so I must consider such a bird. Again, it doesn't exist, but there may exist a bird who thinks there may exist a bird who must consider this bird. This process continues until I must consider a featherless bird who sees no featherless birds. And this lone featherless bird cannot make any conclusions about who has feathers and who doesn't unless it sees a feather. So this chain of hypothetical birds cannot collapse unless a feather exists. And as each night passes, each level of abstraction is ruled out...

Maybe a better way to approach this is "reverse" induction on the number of feathers. If there were 100 feathers. All featherless birds would leave that night. If there were 99 feathers, the featherless birds would stick around one day, seeing 99 featherless birds, and then leave the next night, realizing all featherless birds saw 99 other featherless birds. If there were 98 feathers, then all of the birds would expect all of the birds to stay the first night. But if you're featherless, you consider that birds may leave on the next night (i.e., you assume you have your feather). And when this doesn't happen, you realize there must be at least one more featherless bird, who must be you. Continue in this fashion...

I am wondering if we could be saying "etcetera" too soon. If N=3, a featherless bird looks at the other two featherless birds and could reasonably believe that each believes the other believes N could be equal to 1. But when N=4, none of the birds could possibly believe any other bird thinks N=1. After all, each bird sees 3 featherless friends. So the chain is broken.

I am probably wrong about this, but what am I missing?

He might know that N isn't 1, but he doesn't know that they don't know that N isn't . Not yet. After all, each of those birds might only see two featherless birds.

Originally Posted by MagiMaster

He might know that N isn't 1, but he doesn't know that they don't know that N isn't . Not yet. After all, each of those birds might only see two featherless birds.

If N=4, all birds see at least 3 featherless birds. So each bird, even a featherless one, would have to figure any other bird sees at least 2, eliminating the N=1 possibility. Hence there is no possibility of a bird dying the first night. That breaks the chain.

But not all birds know that all of the birds know that N = 1 is impossible. Namely, a featherless bird cannot rule out that it has a feather, and hence cannot rule out that N = 3. In the N = 3 scenario, a featherless bird cannot rule out that it has a feather, and hence cannot rule out that N = 2. And in the N = 2 scenario, a featherless bird cannot rule out that it has a feather, and hence cannot rule out N = 1. So, in the N = 4 case, a featherless bird must consider that it has a feather (so N = 3), that a featherless bird considers that it has a feather (so N = 2), and that that featherless bird considers that a featherless bird considers that it has a feather (so N = 1). Things get hairier as we go on, but in this scenario we're not too deep as to understand this in English: when N = 4, a featherless bird cannot rule out that one of the featherless birds it sees thinks that a featherless bird may see only one featherless bird. In general, if a bird sees n featherless birds, it cannot rule out that some bird thinks that some other bird may see only n-2 featherless birds.

Originally Posted by serpicojr

But not all birds know that all of the birds know that N = 1 is impossible.

Hold it right there. If all birds know that all other birds see at least 2 featherlesss, yes they certainly can rule out N=1. I know I would if I were one of those birds. Matter of fact, I have almost convinced myself the chain breaks at N=3.

I misspoke... I meant to say, "Not all birds know that all birds know that all birds know that N=1 is impossible." My example was a featherless bird A, which sees three featherless birds B, C, and D, and A must suppose that it has a feather, so, say, in A's mind, B only sees two featherless birds, C and D, and, still in A's mind, B must suppose that it has a feather, so, say, in B's mind in A's mind, C only sees one featherless bird. Of course, this is all hypothetical, and B and C each see three featherless birds. So although A knows that every bird sees at least two featherless birds, A doesn't know that B knows that every bird sees at least two featherless birds, as in A's mind, B may think that C only sees D.

No mas, no mas. I am officially boggled. I'll have to cogitate on this a while longer. I keep coming back to the idea that no bird could possibly expect any other bird to die the first night, so when no bird dies the first night, how does that change any of their calculations.

This thing is still bugging me. I have one other question. Let's say the birds wake up one day and N=100. Each bird sees at least 99 featherless birds and so knows that each other bird sees a minimum of 98 featherless birds. They do not bother to go down to the beach looking for feathers. They already know there are feathers. Let's say there is a "virtual" feather on the beach. Why don't they start their calculations and die on day 100?

Its easier for two birds (IMHO). Say you have two birds, Pete and Fred and both lose their feathers that night. In the morning, pete will wake up and say to himself "poor fred, he lost his feather - if he finds out he will die tonight" and Fred thinks the same thing about pete. Now after that first night, fred and pete bump into each other and neither one is dead.

Now pete thinks the following "fred is not dead which means either he doesn't know he has lost his feather or i have lost my feather!". However, without seeing a feather, pete cannot determine which one of those propositions is true.

Yes, I understand the N=2 situation. I'm just not convinced you can extend it to N=100 or what the fundamental difference is between finding no feathers, one feather, two feathers or whatever when everybody knows that everybody else knows there are feathers.

Suppose I see one feather on the beach and 98 or 99 featherless companions. I may decide to start a sequence of calculations beginning at N=1 but why do I have to assume everybody else starts the same sequence when N is clearly >1? Should I also assume everybody is wondering what would happen if a piece of green cheese fell from the moon?

Edit: If I am a perfect logician then, without going to the beach, I can deduce that there is at least 1 feather on the beach, and every othe bird knows it. This is logically equivalent to a guru making an announcement, or a scuba diver crawling up on the beach, or what have you. Therefore there IS a virtual feather on the beach. Therefore why don't I have to assume that all other birds have done the math and are planning to die on day 99 or 100. When they do not die on day 99, I'm dead meat.

And where is the solution for the puzzle about 3 gods???

Seeing as they are 'logical' people. If there is one who can see 100 brown eyes, 99 blue eyes and the guru. It is simple. The logical person would assume that because there are 100 brown eyed people, and 99 blue eyed people-he/she would naturally assume that he/she has blue eyes.

The genie says-100 of you have brown eyes-100 of you have blue eyes-they are the only colours.

Originally Posted by svwillmer

The genie says-100 of you have brown eyes-100 of you have blue eyes-they are the only colours.

The genie/guru doesn't say that, see the opening post.

This problem is part of epistemic logic (the logic knowledge), you could write up a proof or draw Kripke possible world models (using less people for clearity) of the state of the world after each announcement, which might be easier to understand how the possible solutions/states/worlds disappear after each announcement..

Another great epistemic logic puzzle is the 3 number problem:

Three agents A,B and C all have a positive integer (including 0), x,y and z respectively, pasted on their foreheads. An agent can only see the number on the foreheads of other agents. One of the three numbers is the sum of the two other numbers. All the previous is commonly known to all agents.

The following announcements now take place consecutively:

* A says: "I do not know the numbers."
* B says: "I do not know the numbers."
* C says: "I do not know the numbers."

If the numbers are at most 10, agent A now knows the numbers. Btw, numbers may occur more than once (world in which A=2,B=2,B=4 is an allowed world)

Why does A know the numbers while they only said they didn't know the numbers? What about B and C, do they know the numbers?

Ok then, the person who sees 99 blue eyes and 100 brown eyes is God, so he knows what colour eyes He has because he knows everything!

Even gods aren't allowed to cheat

Awwww =p

Originally Posted by g07g6008

Here is the next one. This riddle was also claimed to be the hardest in the world!

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.


Here are some clarifications:

* It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).

* What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)

* Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

* Random will answer 'da' or 'ja' when asked any yes-no question.

I give up. What's the solution to the puzzle?

Hi Guys

I have thought about this problem and cannot find any solid evidence that you solution is correct.

The islanders do not know that there are 100 blue and 100 brown eyed individuals therefore no matter how long they wait they will never leave the island. If they knew they would have left a long time ago on day 1 or 2 depending on how long it took them to count to 200.

I understand the presumption "thanks to the guru" that after 99 days you have not left because nobody else has because you have blue eyes but you might still have green eyes as well since you do not know that there are 100 of each.

Only we can assume the correct solution as we have all the information. Poor guru is never leaving that island.

Ideas????

Originally Posted by Gavinpitt

Ideas????

You are wrong.
N=1 The only blue eayed islander sees noone else with blue eyes and knows it must be him so he leaves the island.
N=2 They both see the other one with blue eyes and expect him to leave that night. When he does not leave they both know the other one sees another islander with blue eyes. So they both leave the island.
N=3 All three see the other two with blue eyes and expect the other two to realize it in two days as described above. When they don't leave the second night they all know they too have blue eyes. So they leave the island.
N=4 All four see three people with blue eyes. When they don't leave after the third night they know they too have blue eyes and leave the island.
etc.

Thanks for the response.

After a good sleep this all seems logical to me.

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 tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.


Am I losing something here or is the first part of this question flawed and misleading?
Isn't it fixed that there are 100 blue-eyes and 100 brown-eyes? In that case, being perfect logicians, any one blue-eyed person can immediately tell that he is blue-eyed by counting a full 100 for brown-eyes in the first night.


Even if we ignore that and get the essence of the question through the following exemplifications, the introduction of the "red-eyes" possibility is weird too.

So Person A can be blue-eyed/brown-eyed/red-eyed.

If there are 2 people on the island, Person A knows Person B's eye colour, while Person B knows Person A's eye colour.

The Guru announces: "I can see someone who has blue eyes."

Which means that either one of them, or both of them has blue eyes.

However, this also means that the other person can have red/brown eyes. Isn't it practically impossible to deduce one's own eye colour with the introduction of the red-eye possibility?


Or am I understanding this question wrong?

Originally Posted by theSocraticomplex

Isn't it fixed that there are 100 blue-eyes and 100 brown-eyes?

It is, but they don't know that:

as far as he knows the totals could be 101 brown and 99 blue.

Originally Posted by theSocraticomplex

If there are 2 people on the island, Person A knows Person B's eye colour, while Person B knows Person A's eye colour.

The Guru announces: "I can see someone who has blue eyes."

Which means that either one of them, or both of them has blue eyes.

However, this also means that the other person can have red/brown eyes. Isn't it practically impossible to deduce one's own eye colour with the introduction of the red-eye possibility?

It is still possible to deduce whether it's blue or not.