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

En realidad, creo que hay un fallo importante en esta lógica. He visto esto y variantes en el pasado. Entiendo tanto la respuesta de 100 días, como la de 2 días.

Sin embargo

Se omite un dato importante y es lo suficientemente significativo como para afectar a la lógica pasando de 3 a valores mayores de N. Cada dragón sabe que hay al menos 99 dragones de ojos verdes por observación personal. Y sabe que todos los demás dragones saben que hay al menos 98 dragones de ojos verdes (N-2) por observación directa.

La lógica de esto es El dragón 1 piensa "Puedo tener los ojos rojos. Así que el dragón 2-100 esperará que cada uno de ellos tenga los ojos rojos también. Así que ellos sabrían que todos verían uno o dos dragones de ojos rojos. Pero ningún dragón podría pensar lógicamente que cualquier otro dragón podría ver más de dos rojos ya que cada uno debe ver 98 verdes. Y yo sé que en realidad sólo pueden ver uno como máximo porque yo puedo ver 99".

Así que el Dragón 1 sabe que los Dragones 2 a 99 también saben que sólo hay 3 posibilidades como máximo.

1: Todos los ojos verdes

2: El dragón 1 sólo tiene ojos rojos

3: El Dragón 1 y cualquier otro Dragón que esté pensando también tiene los ojos rojos.

Ningún dragón (por ejemplo, el número 1) puede creer que cualquier otro dragón (del 2 al 100) pueda pensar que hay más de dos juegos de ojos rojos. El dragón 1 sabe que la opción 3: no es posible debido a los 99 verdes visibles. Pero el dragón 1 no sabe que los dragones del 2 al 100 lo saben.

Así, el Dragón 1 puede pensar "tengo los ojos rojos y si lo hago cada uno de los otros dragones piensa lo mismo de sí mismo". Si no tengo los ojos rojos, entonces cada uno de los otros dragones puede seguir pensando que puede tener los ojos rojos".

Las extrapolaciones de los valores crecientes de N a partir de 3 no se mantienen. Una simple prueba con sólo 5 dragones lo demuestra. Hay 1 rojo y 4 verdes o 5 verdes. Pero cada dragón individual puede suponer que los otros pueden pensar que hay 2 rojos y 3 verdes. Pero cada dragón sabe que no puede haber menos de 4 verdes y que todos los demás dragones deben saber que no puede haber menos de 3 verdes. La opción de que de alguna manera pueda haber 4 rojos y 1 verde, y que ese verde se vaya el día 1 NO es posible. Como la cadena lógica para N>3 se basa en esto y en los pasos subsiguientes es defectuosa.

Sin embargo, si el rompecabezas se replantea que la persona que se va dice que no hay más de un par de ojos rojos -algo que todos saben, pero que no saben que todos los demás saben- este conocimiento adicional hace que todos obtengan el conocimiento de que cada uno tiene ojos verdes.

Bill