Probabilistic proof of green-eyed dragons logic puzzle

Question

I came across the "green-eyed dragons" puzzle (alternatively known as the "blue eyed villagers" puzzle). The typical proof uses a straightforward inductive strategy. I came up with a probabalistic proof, and I wondered if there are holes in it.

The puzzle in its (possibly original) form can be found here: https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf and the inductive proof here: https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf.

Theorem: All 100 dragons transform at midnight on the first night.

Proof: It suffices to prove that each dragon independently concludes $$\Pr[\textrm{exactly 100 dragons have green eyes}] = 1$$

Upon departing, we tell the dragons collectively that at least one of them has green eyes. Specifically, we impart the knowledge that $$\Pr[\textrm{at least 1 dragon has green eyes}] = 1$$

Define $L_i$ to be the event that at least $i$ dragons have green eyes, and $E_i$ to be the event that exactly $i$ dragons have green eyes.

Then the above probability can be restated as:

\begin{align*} \Pr[L_1] = {100 \choose 1} \Pr[E_1] + {100 \choose 2} \Pr[E_2] + \dots + {100 \choose 100} \Pr[E_{100}] \end{align*}

Because each dragon observes the eye color of every other dragon except himself, each dragon concludes independently that:

\begin{align*} \Pr[E_0] = \Pr[E_1] = \Pr[E_2] = \dots = \Pr[E_{98}] = 0 \end{align*}

Therefore, each dragon concludes

\begin{align*} \Pr[L_1] = {100 \choose 99} \Pr[E_{99}] + \Pr[E_{100}] = 1 \end{align*}

Note that

\begin{align*} \Pr[E_{99}] &= 1-\left(\Pr[E_0] + {100 \choose 1}\Pr[E_1] + \dots + {100 \choose 98}\Pr[E_{98}] + \Pr[E_{100}]\right) \\ &= 1- \Pr[E_{100}] \end{align*}

Therefore, \begin{align*} {100 \choose 99} \Pr[E_{99}] + \Pr[E_{100}] &= 1 \\ 100(1-\Pr[E_{100}]) + \Pr[E_{100}] &= 1 \\ 100 - 99\Pr[E_{100}] &= 1 \\ \Pr[E_{100}] &= 1 \end{align*}

Thus, each dragon individually concludes that with probability 1, all 100 dragons have green eyes (including himself). This reasoning happens simultaneously across all dragons, and thus they all transform together on the first midnight, QED.

Answer 1

I think employing the binomial coefficient $\binom {100} {99}$ is inappropriate here.

$\binom {100} {99} Pr(E_{99})$ is the probability of any one dragon having non-green eyes; however, each dragon knows only one possible dragon has non-green eyes.

Therefore, I think the problem simply reduces to:

$\binom {1} {0} Pr(E_{99}) + \binom {1} {1} Pr(E_{100}) = 1$

Still, awesome attempt.

Answer 2

It doesn't matter how many green-eyed dragons you start with. By stating something about how many there are, you provide a synchronized starting point for all the dragons to use.

Every dragon knows how many dragons there are, and every dragon knows that every other dragon knows this.

If the number of dragons is N where N>2, then every dragon knows that there are at least N-1 green-eyed dragons (not knowing whether each itself has green eyes). Furthermore, every dragon knows that every green-eyed dragon knows that there are at least N-2 green-eyed dragons. (Thus, every situation where the number of green-eyed dragons is less than N-2 can be immediately eliminated from consideration.)

Thus, the first day after the pronouncement, no dragons will transform, because every dragon knows that there are more than N-2 green-eyed dragons, but suspects that a green-eyed dragon might only see N-2 other green-eyed dragons. (It might be worth stating that none of the dragons expects any of them to transform the first night.)

The second day, the dragons know that no dragons transformed, and so learn that no dragon can see only N-2 green-eyed dragons. Each still doesn't know whether it itself has green eyes, but it knows that if there are only N-1 green-eyed dragons, that they would know this today and transform tonight. (Each dragon expects that all the other dragons will transform tonight if it itself does not have green eyes.)

The third day, all the dragons know that none of the other dragons transformed on the second night, so must conclude that all the dragons, including itself, have green eyes. All the dragons will transform on the third night.

The special cases with 1 or 2 dragons will take only 1 or 2 days, respectively, before the transformation of the dragon(s).

---

The blue-eyed villagers/islanders is a bit more complicated, because other eye colors are given as a part of the starting population, but this complication only adds one more day to the maximum solution. (See my answer to this problem on Puzzling.SE.)

Answer 3

This is a problem about knowledge, not about probability. When the traveller leaves, they all know that at least one dragon has green eyes. If there had been only one such dragon, that dragon would know they had green eyes and would transform at midnight.

The next morning all the dragons know that no dragon transformed at midnight. They therefore also know that there are at least two dragons with green eyes. If there were exactly two, they would transform at midnight. It doesn't happen, so the next morning the dragons know that there are at least three dragons with green eyes.

The information that no dragons transform in the night is additional information not present on the first day. A dragon does not know whether or not it has green eyes until ninety nine nights have passed. If it hasn't got green eyes, the others will all transform on the ninety ninth night. If it does have green eyes, they will all transform on the hundredth night.

Since these two possibilities are live, no dragon can conclude on the first night that all dragons have green eyes.

Answer 4

This is a game theory question that needs no probability to figure it out since dragons will only transform when they know completely know that they have green eyes not likely odds that they have them), the answer is if there are $n$ dragons,on the $n$th night they will all transform.

To get this answer, start with the base case $n=2$ then use induction to work your way up.

Also in your proof, you state that $$P[E_{99}]=1-P[E_{100}]$$ But it should be that $${100 \choose 99}P[E_{99}]=1-P[E_{100}]$$ using this will yield that $1=1$ (which means we basically dont know about these anything of these probabilities anyways versus $P[E_{100}]=1$.

Answer 5

Actually I think there is a major flaw in this logic. I have seen this and variants in the past. I understand both the 100 day answer, and the 2 day answer.

However -

One important datum is omitted and it is significant enough to affect the logic going from 3 up to larger values for N. Each dragon knows there are at least 99 green eyed dragons from personal observation. And he/she knows that every other dragon knows there are at least 98 green-eyed dragons (N-2) from direct observation.

The logic for this is Dragon 1 thinks “I may have red eyes. So dragon 2-100 will hope that each of them has red eyes too. So thus they would know that all would see either one or two red eyeds dragons. But no dragon could logically think any other dragon could sees more than two reds as threy must each see 98 greens. And I know they really can only see one at most because I cam see 99.”

So Dragon 1 knows that Dragons 2 to 99 also know there are only 3 possibilities at most.

1: All green eyes

2: Dragon 1 only has red eyes

3: Dragon 1 and whichever other Dragon is thinking also has red eyes.

No dragon (eg number 1) can believe any other dragon (2 to 100) could think there are more than two sets of red eyes. Dragon 1 knows that option 3: is not possible because of the 99 greens visible. But Dragon 1 does not know that Dragons 2-100 know that.

So Dragon 1 can think “I have red eyes and if I do each of the other dragons thinks the same of themselves. If I don’t have red eyes, then each other dragon may still think they may have red eyes.”

The extrapoloations of increasing N values from 3 up do not hold. A simple test with only 5 dragons shows this. There are either 1 red and 4 green or 5 green. But each individual dragon can assume the others may think there are 2 red and 3 green. But each dragon knows there can not be less than 4 greens and that all other dragons must know there can not be less than 3 greens. The option that somehow there could be 4 reds and 1 green, And that green would then leave on day 1 is NOT possible. As the logic chain for N>3 relies on this And subsequent steps it is flawed.

However if the puzzle was restated that the person leaving said there is no more than one set of red eyes - something they all know, but which they dont know all the others know - this extra knowledge triggers them all to get the knowledge that they each have green eyes.

Bill

Answer 6

Each dragon tells to his first neighbor: "You have green eyes". As soon as this neighbor dragon heard that, he transformed to a swallow and flew away from the island. At the end only one dragon left on the island, namely that dragon who was the latest candidate to hear the information about the green color of his eyes. No mathematical proof is needed!