The "hardest logic puzzle in the world"

[TheOriginalHappyGoat]

Haven't shared much from 538's Riddler lately, because they've all been poorly disguised algebra problems. So here's an oldie, a legit logic puzzle that really makes you think. It's been called by some the most difficult logic puzzle ever. Answers is spoilers, please.

You visit a remote desert island inhabited by one hundred very friendly dragons, all of whom have green eyes. They haven't seen a human for many centuries and are very excited about your visit. They show you around their island and tell you all about their dragon way of life (dragons can talk, of course).

They seem to be quite normal, as far as dragons go, but then you find out something rather odd. They have a rule on the island which states that if a dragon ever finds out that he/she has green eyes, then at precisely midnight on the day of this discovery, he/she must relinquish all dragon powers and transform into a long-tailed sparrow. However, there are no mirrors on the island, and they never talk about eye color, so the dragons have been living in blissful ignorance throughout the ages.

Upon your departure, all the dragons get together to see you off, and in a tearful farewell you thank them for being such hospitable dragons. Then you decide to tell them something that they all already know (for each can see the colors of the eyes of the other dragons). You tell them all that at least one of them has green eyes. Then you leave, not thinking of the consequences (if any). Assuming that the dragons are (of course) infallibly logical, what happens?

If something interesting does happen, what exactly is the new information that you gave the dragons?

 

[i'vegotwinners]

no idea how to do the "spoiler alert" thing.

that said, an obvious sort of "mutually exclusive" type conundrum thing with the scenario as presented. (2 actually).

not sure if the conundrum is merely a side note or not.

how do i post without showing.

 

[TheOriginalHappyGoat]

no idea how to do the "spoiler alert" thing.

that said, an obvious sort of "mutually exclusive" type conundrum thing with the scenario as presented. (2 actually).

not sure if the conundrum is merely a side note or not.

how do i post without showing.

On the reply box, the icons at top, next to the picture and the movie is a + sign. Click on that and select spoiler. Name it if you want. Once it's inserted, put your answer inside the spoiler tags.

Edit:
Your text should look like this:

[spoiler]
Etc. etc. whatever you want to say
[/spoiler]

 

[Hank Reardon]

Spoiler

Well, it seems to me that you're not telling them something that they don't already know. Unless they don't know what green looks like. Perhaps they assume that whatever color their eyes are, that's not green. And being told that at least one has green eyes, they'd all assume that if the others aren't green, theirs must be. So I suppose they all turn into sparrows.

This probably isn't correct, and if it is it seems sort of a weak explanation since it requires us to assume some fact not shared in the puzzle.

 

[TheOriginalHappyGoat]

Spoiler

Well, it seems to me that you're not telling them something that they don't already know. Unless they don't know what green looks like. Perhaps they assume that whatever color their eyes are, that's not green. And being told that at least one has green eyes, they'd all assume that if the others aren't green, theirs must be. So I suppose they all turn into sparrows.

This probably isn't correct, and if it is it seems sort of a weak explanation since it requires us to assume some fact not shared in the puzzle.

Well...

Spoiler: Wrongish

Your gut is pushing you in the right direction, but your reasoning is way off. Hint: your statement to the dragons really does give them new information. That is important. The trick is figuring out what that new information is. Then the answer comes to you.

Spoiler: Hint

Think about what your statement would mean if there were only two dragons on the island.

 

[Hank Reardon]

Well...

Spoiler: Hint

Think about what your statement would mean if there were only two dragons on the island.

Spoiler

Well, if there were only two dragons and they could see each other, then they'd know because if the other didn't turn into a sparrow, then YOUR eyes must be green. Because if your eyes weren't, the other would know theirs had to be. But I'm having a hard time applying that to 100 dragons.

 

[Marvin the Martian]

Spoiler: I do not think I like the answer

The best I can come up with is at some point all dragons will realize they have green eyes and change. I think the assumption will be that if I had brown eyes, someone would tell me. If that is the answer, I do not like it as the puzzle clearly indicates dragons never talk eye color.

So it should be nothing happens, but that is not much of a puzzler.

 

[TheOriginalHappyGoat]

Spoiler

Well, if there were only two dragons and they could see each other, then they'd know because if the other didn't turn into a sparrow, then YOUR eyes must be green. Because if your eyes weren't, the other would know theirs had to be. But I'm having a hard time applying that to 100 dragons.

Okay, then.

Spoiler: Next hint

You're absolutely right about what would happen with two dragons. The trick is then thinking about how that would work with three dragons. Then it just cascades.

 

[TheOriginalHappyGoat]

Spoiler: I do not think I like the answer

The best I can come up with is at some point all dragons will realize they have green eyes and change. I think the assumption will be that if I had brown eyes, someone would tell me. If that is the answer, I do not like it as the puzzle clearly indicates dragons never talk eye color.

So it should be nothing happens, but that is not much of a puzzler.

Nope.

Spoiler: Hint

You're right that would be a bad puzzler. Something definitely happens. And your gut is pushing you toward what that is.

Think about what would happen if there were only two dragons, then expand from there.

 

[Hank Reardon]

Okay, then.

Spoiler: Next hint

You're absolutely right about what would happen with two dragons. The trick is then thinking about how that would work with three dragons. Then it just cascades.

Spoiler

Eh, I'm having a tough time applying that to three or more since you've only told them that "at least one" has green eyes. If there are three, there is no basis to determine your own eyes based on the actions of the others. Or at least I can't see how. If each can see two other dragons with green eyes, then they'd know that each of the others could see at least one. So how would anyone determine their own eyes based on the others' actions?

Obviously I'm missing something.

 

[TheOriginalHappyGoat]

Spoiler

Eh, I'm having a tough time applying that to three or more since you've only told them that "at least one" has green eyes. If there are three, there is no basis to determine your own eyes based on the actions of the others. Or at least I can't see how. If each can see two other dragons with green eyes, then they'd know that each of the others could see at least one. So how would anyone determine their own eyes based on the others' actions?

Obviously I'm missing something.

I don't want to give the whole thing away.

Spoiler: Try this

Think about not only what a dragon knows, but what he knows other dragons know.

 

[Marvin the Martian]

Nope.

Spoiler: Hint

You're right that would be a bad puzzler. Something definitely happens. And your gut is pushing you toward what that is.

Think about what would happen if there were only two dragons, then expand from there.

Spoiler: I don't buy it

It does not scale. At 2 it makes sense if you do not change, you must see that I have green. At 100 there is always plausible deniability. There could be anywhere from 0 to 99 dragons with other eye color. Just because the other 99 do not change is not proof I have green eyes as even if I have brown that is no reason for you to believe you must have green.

 

[TheOriginalHappyGoat]

Spoiler: I don't buy it

It does not scale. At 2 it makes sense if you do not change, you must see that I have green. At 100 there is always plausible deniability. There could be anywhere from 0 to 99 dragons with other eye color. Just because the other 99 do not change is not proof I have green eyes as even if I have brown that is no reason for you to believe you must have green.

Nope.

Spoiler: Do the pencil and paper

You're right that it doesn't obviously scale. But it does scale if you really work down to the nitty-gritty. Work out exactly what would happen with three dragons, and if you can figure out why that happens, you'll have the answer.

 

[TheOriginalHappyGoat]

Spoiler: I don't buy it

It does not scale. At 2 it makes sense if you do not change, you must see that I have green. At 100 there is always plausible deniability. There could be anywhere from 0 to 99 dragons with other eye color. Just because the other 99 do not change is not proof I have green eyes as even if I have brown that is no reason for you to believe you must have green.

BTW, I saw a tweet from someone about this puzzle that said, "It only works with up to six dragons. More than six, I can't figure it out."

 

[Hank Reardon]

I don't want to give the whole thing away.

Spoiler: Try this

Think about not only what a dragon knows, but what he knows other dragons know.

Spoiler

Well, that the thing. Each dragon knows that the other two have green eyes. Therefore each dragon knows that the other two dragons must know that at least one has green eyes. Now I suppose that, since neither of the other turns (as would happen if I had brown eyes and one of the others had brown eyes, then I must have green eyes since neither of the others assumes their own color based on the actions of the other dragons.

OK. I get it. But those are some smart dragons.

 

[TheOriginalHappyGoat]

Spoiler

Well, that the thing. Each dragon knows that the other two have green eyes. Therefore each dragon knows that the other two dragons must know that at least one has green eyes. Now I suppose that, since neither of the other turns (as would happen if I had brown eyes and one of the others had brown eyes, then I must have green eyes since neither of the others assumes their own color based on the actions of the other dragons.

OK. I get it. But those are some smart dragons.

You're getting close.

Spoiler: This is a killer spoiler. Don't read unless you are really stumped.

Let's say there are three dragons. Put yourself in one of the dragon's shoes. Assume you don't have green eyes. What happens?

Night 1: Nothing. Both the other dragons see each other's green eyes, and they don't transform.

Night 2: Here is the trick. If you have, say, blue eyes, then after no one transformed on Night 1, the other dragons should realize they also have green eyes (because they should realize that they didn't transform because they were looking at each other). So they should transform.

But they don't. Which can only mean one thing: you also have green eyes.

Since this same logic applies to the other dragons, as well, all three of you realize on the third day that you have green eyes, and all transform at the same time, on Night 3.

 

[Hank Reardon]

You're getting close.

Spoiler: This is a killer spoiler. Don't read unless you are really stumped.

Let's say there are three dragons. Put yourself in one of the dragon's shoes. Assume you don't have green eyes. What happens?

Night 1: Nothing. Both the other dragons see each other's green eyes, and they don't transform.

Night 2: Here is the trick. If you have, say, blue eyes, then after no one transformed on Night 1, the other dragons should realize they also have green eyes (because they should realize that they didn't transform because they were looking at each other). So they should transform.

But they don't. Which can only mean one thing: you also have green eyes.

Since this same logic applies to the other dragons, as well, all three of you realize on the third day that you have green eyes, and all transform at the same time, on Night 3.

I suppose the most important aspect to remember is that dragons have a much greater capacity for logical thought than the averag coolerite.

 

[Digressions]

Spoiler: I don't buy it

It does not scale. At 2 it makes sense if you do not change, you must see that I have green. At 100 there is always plausible deniability. There could be anywhere from 0 to 99 dragons with other eye color. Just because the other 99 do not change is not proof I have green eyes as even if I have brown that is no reason for you to believe you must have green.

I agree with Marvin. What new information was given to the dragons? I think that is the key. Unless, the dragons don't know what the color green is?

 

[TheOriginalHappyGoat]

I agree with Marvin. What new information was given to the dragons? I think that is the key. Unless, the dragons don't know what the color green is?

There was definitely new information given to them.

 

[Digressions]

There was definitely new information given to them.

What was it?

 

[TheOriginalHappyGoat]

What was it?

Spoiler: Spoiler

The new information given to each dragon was about what the other dragons now know. Or, more accurately, what the other dragons now know that the other dragons know.

 

[i'vegotwinners]

Spoiler: spoiler

question, define "exactly midnight".

we write it 12:00 am.

can midnight end a day, or only begin one, or both.

also,

"Then you decide to tell them something that they all already know"

"what exactly is the new information that you gave the dragons"?

a contradiction?

 

[i'vegotwinners]

Spoiler: spoiler

by telling them that at least one of them had green eyes, did you in doing so, define to them what "green" was?

 

[Marvin the Martian]

Spoiler: In theory

The idea none have green eyes has been eliminated. Not just that, but now they all know that. It eliminates that part of plausible deniability. I still think it breaks down at some number.

 

[TheOriginalHappyGoat]

Spoiler: spoiler

by telling them that at least one of them had green eyes, did you in doing so, define to them what "green" was?

Nope. See spoilers I already posted.

 

[TheOriginalHappyGoat]

Spoiler: In theory

The idea none have green eyes has been eliminated. Not just that, but now they all know that. It eliminates that part of plausible deniability. I still think it breaks down at some number.

A common sense response. But wrong.

When you get the answer, it's a...well, not a "Ah Ha!" moment, but more of a "Jesus. Of course. That sucks" moment.

 

[Digressions]

Spoiler: I don't buy it

It does not scale. At 2 it makes sense if you do not change, you must see that I have green. At 100 there is always plausible deniability. There could be anywhere from 0 to 99 dragons with other eye color. Just because the other 99 do not change is not proof I have green eyes as even if I have brown that is no reason for you to believe you must have green.

Spoiler: Dear Marvin

Plausible deniability is the exact phrase that came to my mind too.

 

[iu_a_att]

Spoiler: But what if one of the dragons can't do logic

Consider the case of two entirely logical dragons who both know they are logical and both know they both know etc...and both have green eyes. They each look at each other's eyes then on night one if neither dragon turns into a sparrow then each knows that the other has seen green eyes because otherwise the one who didn't see green eyes would turn into a sparrow. Sot the next night they both turn into sparrows.
But, suppose they both also know that there is a small probability one of them is bad at logic and can't solve the problem. Suppose both are actually good at logic. I think in this case the dragons live happily ever after as dragons because, even if they are both actually good at logic, they can't be sure that the other one isn't good at logic and so doesn't know to turn into a sparrow on the first night.

 

[Marvin the Martian]

Spoiler: If there are 4 dragons

I am dragon D. I can see that A, B, and C have green eyes. That tells me that dragon A can see at least two dragons with green eyes, as can B and C. After 4 nights, there is no reason to suddenly know I have green eyes. I know that dragon A can see B and C and thus the condition "At least one has green eyes" has been met. I know B can see A and C and again the condition has been met. I know C can see A and B and again the condition has been met. There is no reason to suddenly deduce "I am the reason they have not changed to birds". The reason is already there, each dragon can easily conclude the other dragons have reasonable doubt. That does go away at 2 dragons. But at larger numbers, each dragon can see reasonable doubt.

 

[TheOriginalHappyGoat]

Spoiler: If there are 4 dragons

I am dragon D. I can see that A, B, and C have green eyes. That tells me that dragon A can see at least two dragons with green eyes, as can B and C. After 4 nights, there is no reason to suddenly know I have green eyes. I know that dragon A can see B and C and thus the condition "At least one has green eyes" has been met. I know B can see A and C and again the condition has been met. I know C can see A and B and again the condition has been met. There is no reason to suddenly deduce "I am the reason they have not changed to birds". The reason is already there, each dragon can easily conclude the other dragons have reasonable doubt. That does go away at 2 dragons. But at larger numbers, each dragon can see reasonable doubt.

You're missing one key thing:

Spoiler: Try this

You need to realize what you as Dragon D learn each time a night passes with no transformations. Think about this: what would happen if only two of the dragons had green eyes? Three? Etc.

 

[iu_a_att]

Spoiler: hint proof by induction

Step 1. Find some set of dragons with green eyes of size n such that it takes them n nights to determine that they all have green eyes. (Hint, make this initial step as easy for yourself as possible).

Step 2. Show that if you add a dragon without green eyes to the set of n then it still takes n nights for that initial set to learn they all have green eyes. But if the added dragon also has green eyes then on the nth night all the initial dragons don't turn into sparrows. But then they must all turn into sparrows on the n+1th night.

The new information that the visitors statement creates is the knowledge of the fact that at least one has green eyes. Without that knowledge step 1 fails.

I do think it is interesting that this result requires what game theorists call "common knowledge" of perfect rationality. If only the visitor had said to the dragons that there is some small chance that at least one of you can't draw logical inferences then the dragons would be fine.

 

[TheOriginalHappyGoat]

Spoiler: hint proof by induction

Step 1. Find some set of dragons with green eyes of size n such that it takes them n nights to determine that they all have green eyes. (Hint, make this initial step as easy for yourself as possible).

Step 2. Show that if you add a dragon without green eyes to the set of n then it still takes n nights for that initial set to learn they all have green eyes. But if the added dragon also has green eyes then on the nth night all the initial dragons don't turn into sparrows. But then they must all turn into sparrows on the n+1th night.

The new information that the visitors statement creates is the knowledge of the fact that at least one has green eyes. Without that knowledge step 1 fails.

I do think it is interesting that this result requires what game theorists call "common knowledge" of perfect rationality. If only the visitor had said to the dragons that there is some small chance that at least one of you can't draw logical inferences then the dragons would be fine.

Spoiler: Good, but

Your proof by induction works, and it is the best way to solve it, but your take on exactly what new information was communicated is incorrect. In any case in which the number of dragons with green eyes is greater than one, as it is here, they all already know that at least one of them has green eyes. So the new information must be something different.

(Think about the special case of two green-eyed dragons, and you'll probably get it, but scaling it up to 100 might break your brain.)

 

[iu_a_att]

Spoiler: Good, but

Your proof by induction works, and it is the best way to solve it, but your take on exactly what new information was communicated is incorrect. In any case in which the number of dragons with green eyes is greater than one, as it is here, they all already know that at least one of them has green eyes. So the new information must be something different.

(Think about the special case of two green-eyed dragons, and you'll probably get it, but scaling it up to 100 might break your brain.)

Spoiler: proof by induction doesn't work without the new information

I say the induction proof doesn't work without the new information. In particular. Consider the case with 1 dragon. Without the knowledge that at least one dragon has green eyes that dragon never turns into a sparrow. Now consider the case with two dragons both with green eyes. Without the knowledge that one has green eyes neither dragon would ever, even if the other didn't have green eyes, leave the first night. So neither will leave on the second or the third. Even if it were true that the induction step worked...that is: given that n with green eyes leave on the nth night thus n+1 with green eyes leave on the n+1th night...there is no way that I know to start the sequence. So the proof doesn't work.

 

[TheOriginalHappyGoat]

Spoiler: proof by induction doesn't work without the new information

I say the induction proof doesn't work without the new information. In particular. Consider the case with 1 dragon. Without the knowledge that at least one dragon has green eyes that dragon never turns into a sparrow. Now consider the case with two dragons both with green eyes. Without the knowledge that one has green eyes neither dragon would ever, even if the other didn't have green eyes, leave the first night. So neither will leave on the second or the third. Even if it were true that the induction step worked...that is: given that n with green eyes leave on the nth night thus n+1 with green eyes leave on the n+1th night...there is no way that I know to start the sequence. So the proof doesn't work.

Spoiler: That's not the point.

You are right about the proof. You are wrong about what exactly the new information is. As long as there are at least two green-eyed dragon, then every dragon already knows there is at least one with green eyes. So that can't be the new info. But by saying this out loud to all of them (hint), he also bestowed upon them some other information, and it is this piece of information that actually allows everything to happen.

It's already sitting there in your proof; you're just not recognizing it.

 

[iu_a_att]

Spoiler: That's not the point.

You are right about the proof. You are wrong about what exactly the new information is. As long as there are at least two green-eyed dragon, then every dragon already knows there is at least one with green eyes. So that can't be the new info. But by saying this out loud to all of them (hint), he also bestowed upon them some other information, and it is this piece of information that actually allows everything to happen.

It's already sitting there in your proof; you're just not recognizing it.

Spoiler: reply

I thought I was saying that but let me try to say it a bit more precisely. I am saying the new information is that it is necessarily the case that at least one dragon has green eyes. While one dragon observing the other knows that there is at least one dragon with green eyes. Neither dragon knows that the other dragon knows this. Let's consider the case with two dragons. The knowledge that at least one necessarily has green eyes is combined with the (counterfactual) knowledge that if only one dragon has green eyes then that Dragon would learn that fact immediately and turn into a sparrow. The new knowledge is only helpful in the counterfactual condition in which one of the two dragons does not have green eyes. Without that knowledge nothing happens in the counterfactual condition.

 

[TheOriginalHappyGoat]

Spoiler: reply

I thought I was saying that but let me try to say it a bit more precisely. I am saying the new information is that it is necessarily the case that at least one dragon has green eyes. While one dragon observing the other knows that there is at least one dragon with green eyes. Neither dragon knows that the other dragon knows this. Let's consider the case with two dragons. The knowledge that at least one necessarily has green eyes is combined with the (counterfactual) knowledge that if only one dragon has green eyes then that Dragon would learn that fact immediately and turn into a sparrow. The new knowledge is only helpful in the counterfactual condition in which one of the two dragons does not have green eyes. Without that knowledge nothing happens in the counterfactual condition.

You're almost there.

Spoiler: I think

I think you actually get it, but you're saying it wrong. It has nothing to do with knowing that at least one dragon has green eyes. It would matter in your counterfactual, yes, but so long as n > 1, everyone already knows that. You mentioned that they might not know that the other dragon knows there is at least one with green eyes. That is the key. Formalize that for n dragons and you have identified the new information that screws them all over (it's easy to describe for n = 2, but trickier for n = 3 or more).

 

[Marvin the Martian]

You're almost there.

Spoiler: I think

I think you actually get it, but you're saying it wrong. It has nothing to do with knowing that at least one dragon has green eyes. It would matter in your counterfactual, yes, but so long as n > 1, everyone already knows that. You mentioned that they might not know that the other dragon knows there is at least one with green eyes. That is the key. Formalize that for n dragons and you have identified the new information that screws them all over (it's easy to describe for n = 2, but trickier for n = 3 or more).

Spoiler: spoiler

Assuming no blind dragons, every dragon knows at least 99 dragons have green eyes. I think Mr. Spock would find it highly illogical to look at a population one is in that all have one characteristic the same and then assume one does not share that characteristic. If the dragons were already logical, they would have already been swallows.

 

[Noodle]

Spoiler: Spoiler

To simplify things, I will refer to the non-green eyed dragons red eyed dragons.

N = 3, there are three possibilities:
1 green eyed
2 green eyed
3 green eyed

If there were only one green eyed, then that dragon turns the very first night (since that dragon would only see red eyed dragons). If no one turns the first night, they all know that there are either 2 or 3 green eyed.

If there were only two green eyed, then both of those would turn the second night since each would see that one of the other two is red eyed (i.e., they know that they have to be green eyed). Once no one turns the second night, then they all know that they all are green eyed and they turn the third night.

N=4, there are four possibilities:
1 green eyed
2 green eyed
3 green eyed
4 green eyed

If there were only one green eyed, then that dragon would turn the very first night (since that dragon would only see red eyed dragons). Once no one turns the first night, they all know that there are either 2, 3 or 4 green eyed.

If there were only two green eyed, then both of those would turn the second night since each would see only one other green eyed (therefore, knowing that they are one of the green eyed).

Once no one turns the second night, they all know that either 3 or 4 of them are green eyed. If 3 of them were green eyed, then all three of them would turn the third night, since they would only see 2 other green eyed. Once no on turns on the third night, they all know that they are all green eyed and turn on the fourth night.

You can repeat this same process for any number of dragons. So, the answer is that all 100 dragons turn into birds on the 100th night following my departure.

 

[iu_a_att]

You're almost there.

Spoiler: I think

I think you actually get it, but you're saying it wrong. It has nothing to do with knowing that at least one dragon has green eyes. It would matter in your counterfactual, yes, but so long as n > 1, everyone already knows that. You mentioned that they might not know that the other dragon knows there is at least one with green eyes. That is the key. Formalize that for n dragons and you have identified the new information that screws them all over (it's easy to describe for n = 2, but trickier for n = 3 or more).

Spoiler: I think I have been saying this all along

I think we have been agreeing about what the key information is: the counterfactual is key. The question is not what the other dragons know...the question is what they know about what the other dragons know.

 

[TheOriginalHappyGoat]

Spoiler: Spoiler

To simplify things, I will refer to the non-green eyed dragons red eyed dragons.

N = 3, there are three possibilities:
1 green eyed
2 green eyed
3 green eyed

If there were only one green eyed, then that dragon turns the very first night (since that dragon would only see red eyed dragons). If no one turns the first night, they all know that there are either 2 or 3 green eyed.

If there were only two green eyed, then both of those would turn the second night since each would see that one of the other two is red eyed (i.e., they know that they have to be green eyed). Once no one turns the second night, then they all know that they all are green eyed and they turn the third night.

N=4, there are four possibilities:
1 green eyed
2 green eyed
3 green eyed
4 green eyed

If there were only one green eyed, then that dragon would turn the very first night (since that dragon would only see red eyed dragons). Once no one turns the first night, they all know that there are either 2, 3 or 4 green eyed.

If there were only two green eyed, then both of those would turn the second night since each would see only one other green eyed (therefore, knowing that they are one of the green eyed).

Once no one turns the second night, they all know that either 3 or 4 of them are green eyed. If 3 of them were green eyed, then all three of them would turn the third night, since they would only see 2 other green eyed. Once no on turns on the third night, they all know that they are all green eyed and turn on the fourth night.

You can repeat this same process for any number of dragons. So, the answer is that all 100 dragons turn into birds on the 100th night following my departure.

That is all good...

Spoiler: But...

First of all, good job even figuring that much out. Most people don't. But can you adequately explain why, by answering the last question? What was the new information the visitor gave the dragons when he made his statement? That's the part that is really hard to wrap your head around.