Prueba probabilística del acertijo lógico de los dragones de ojos verdes

Question

Me encontré con el rompecabezas de los "dragones de ojos verdes" (también conocido como el rompecabezas de los "aldeanos de ojos azules"). La prueba típica utiliza una estrategia inductiva directa. Se me ocurrió una prueba probabilística, y me pregunté si hay agujeros en ella.

El rompecabezas en su forma (posiblemente original) se puede encontrar aquí: https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf y la prueba inductiva aquí: https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf .

Teorema : Los 100 dragones se transforman a medianoche de la primera noche.

Prueba : Basta con demostrar que cada dragón concluye independientemente $$\Pr[\textrm{exactly 100 dragons have green eyes}] = 1$$

Al partir, les decimos a los dragones colectivamente que al menos uno de de ellos tiene los ojos verdes. En concreto, les comunicamos que $$\Pr[\textrm{at least 1 dragon has green eyes}] = 1$$

Definir $L_i$ para ser el evento que al menos $i$ los dragones tienen ojos verdes, y $E_i$ para ser el evento que exactamente $i$ los dragones tienen ojos verdes.

Entonces la probabilidad anterior se puede replantear como

\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*}

Como cada dragón observa el color de los ojos de todos los demás dragones, excepto el suyo, cada dragón concluye de forma independiente que:

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

Por lo tanto, cada dragón concluye

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

Tenga en cuenta que

\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*}

Por lo tanto, \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*}

Así, cada dragón concluye individualmente que con probabilidad 1, todos 100 dragones tienen ojos verdes (incluido él mismo). Este razonamiento ocurre simultáneamente en todos los dragones, y así todos se transforman juntos en la primera medianoche, QED.

Answer 1

Este es un problema de conocimiento, no de probabilidad. Cuando el viajero se va, todos saben que al menos un dragón tiene los ojos verdes. Si sólo hubiera uno de esos dragones, ese dragón sabría que tiene los ojos verdes y se transformaría a medianoche.

A la mañana siguiente todos los dragones saben que ningún dragón se transformó a medianoche. Por lo tanto, también saben que hay al menos dos dragones con ojos verdes. Si hubiera exactamente dos, se transformarían a medianoche. Esto no ocurre, así que a la mañana siguiente los dragones saben que hay al menos tres dragones con ojos verdes.

La información de que no hay dragones que se transformen por la noche es una información adicional que no está presente en el primer día. Un dragón no sabe si tiene o no ojos verdes hasta que han pasado noventa y nueve noches. Si no tiene ojos verdes, todos los demás se transformarán en la nonagésima novena noche. Si tiene ojos verdes, todos se transformarán en la centésima noche.

Como estas dos posibilidades están vivas, ningún dragón puede concluir en la primera noche que todos los dragones tienen los ojos verdes.

Answer 2

No importa con cuántos dragones de ojos verdes empieces. Al indicar algo sobre cuántos hay, proporcionas un punto de partida sincronizado para que todos los dragones lo utilicen.

Todo dragón sabe cuántos dragones hay, y todo dragón sabe que todos los demás dragones lo saben.

Si el número de dragones es N donde N>2, entonces cada dragón sabe que hay al menos N-1 dragones de ojos verdes (sin saber si cada uno de ellos tiene ojos verdes). Además, todo dragón sabe que todo dragón de ojos verdes sabe que hay al menos N-2 dragones de ojos verdes. (Por lo tanto, toda situación en la que el número de dragones de ojos verdes sea inferior a N-2 puede eliminarse inmediatamente de la consideración).

Así, el primer día después del pronunciamiento, ningún dragón se transformará, porque cada dragón sabe que hay más de N-2 dragones de ojos verdes, pero sospecha que un dragón de ojos verdes sólo puede ver a otros N-2 dragones de ojos verdes. (Quizá convenga decir que ninguno de los dragones espera que ninguno se transforme la primera noche).

El segundo día, los dragones saben que no hay dragones transformados, y así aprenden que ningún dragón puede ver sólo N-2 dragones de ojos verdes. Cada uno todavía no sabe si tiene ojos verdes, pero sabe que si sólo hay N-1 dragones de ojos verdes, lo sabrán hoy y se transformarán esta noche. (Cada dragón espera que todos los demás dragones se transformen esta noche si él mismo no tiene los ojos verdes).

Al tercer día, todos los dragones saben que ninguno de los otros dragones se transformó en la segunda noche, por lo que deben concluir que todos los dragones, incluido él mismo, tienen los ojos verdes. Todos los dragones se transformarán en la tercera noche.

Los casos especiales con 1 o 2 dragones tardarán sólo 1 o 2 días, respectivamente, antes de la transformación del dragón o dragones.

---

Lo de los aldeanos/insulares de ojos azules es un poco más complicado, porque se dan otros colores de ojos como parte de la población inicial, pero esta complicación sólo añade un día más a la solución máxima. (Ver mi respuesta a este problema en Puzzling.SE.)

Answer 3

Creo que emplear el coeficiente binomial $\binom {100} {99}$ es inapropiado aquí.

$\binom {100} {99} Pr(E_{99})$ es la probabilidad de que cualquier dragón tenga ojos no verdes; sin embargo, cada dragón sabe que sólo un posible dragón tiene ojos no verdes.

Por lo tanto, creo que el problema se reduce simplemente a:

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

Aun así, un intento impresionante.

Answer 4

Esta es una pregunta de teoría de juegos que no necesita probabilidad para resolverla ya que los dragones sólo se transformarán cuando sepan completamente que tienen ojos verdes no probabilidades de que los tengan), la respuesta es si hay $n$ dragones, en el $n$ La noche en que todos se transformarán.

Para obtener esta respuesta, comience con el caso base $n=2$ y luego utilizar la inducción para trabajar su camino hacia arriba.

También en su prueba, usted afirma que $$P[E_{99}]=1-P[E_{100}]$$ Pero debería ser que $${100 \choose 99}P[E_{99}]=1-P[E_{100}]$$ utilizando esto dará como resultado que $1=1$ (lo que significa que básicamente no sabemos nada de estas probabilidades de todos modos versus $P[E_{100}]=1$ .

Answer 5

Cada dragón se lo cuenta a su primer vecino: "Tienes los ojos verdes". En cuanto este dragón vecino lo oyó, se transformó en golondrina y salió volando de la isla. Al final sólo queda un dragón en la isla, el que fue el último candidato en escuchar la información sobre el color verde de sus ojos. ¡No hace falta ninguna prueba matemática!