El problema de las 100 cárceles- ¿Por qué no funciona esta solución?

Question

Hay un acertijo combinatorio que dice lo siguiente: En este problema, 100 prisioneros numerados deben encontrar sus propios números en uno de los 100 cajones para sobrevivir. Las reglas establecen que cada prisionero sólo puede abrir 50 cajones y no puede comunicarse con otros prisioneros.

La mejor solución encontrada hasta ahora es aquella en la que: 1. Cada prisionero abre primero el cajón con su propio número. 2. Si este cajón contiene su número ha terminado y ha tenido éxito. 3. En caso contrario, el cajón contiene el número de otro preso y éste abre a continuación el cajón con este número. 4. El prisionero repite los pasos 2 y 3 hasta que encuentre su propio número o haya abierto 50 cajones.

Mediante este proceso, mientras no exista un ciclo de más de 50, hay una probabilidad bastante alta (aproximadamente el 30%) de que los presos tengan éxito. Esto se debe a que hay un 70% de posibilidades de que exista un ciclo de 51 o más.

Al intentar calcular la probabilidad de que haya un ciclo de 51 o más, hice que un preso empezara por su propio cajón. La probabilidad de que el cajón no contenga su número debería ser de 99/100. En tal caso, va al segundo cajón (cuyo número se encontró en el primer cajón). La probabilidad de que este cajón no contenga su número es de 98/99. Por tanto, la probabilidad de que pase por 51 o más cajones antes de encontrar su propio número, supongo, debería ser de 99/100 * 98/99 * 97/98 *...*49/50. Por lo tanto, la probabilidad de que haya un ciclo de tamaño 51 o más por esta cadena de razonamiento sería de 49/100.

Esperaba preguntar si alguien de aquí podría indicarme el fallo en mi línea de razonamiento.

Gracias.

Answer 1

Su defecto es algo similar a la paradoja de cumpleaños : cada uno particular prisionero tiene una probabilidad de 49/100 de estar en una cadena de 51 o más. Pero la probabilidad de al menos uno El prisionero que se encuentra en una cadena de 51 o más es alrededor del 70%. Pasar de los dos primeros a los segundos es complicado, porque las probabilidades no son independientes: si un preso está en un ciclo de 51 o más, entonces al menos otros 50 presos también están en ciclos de 51 o más.

Answer 2

Permítanme proporcionar un método para calcular el número de permutaciones en $S_{n}$ que contienen un $k$ -ciclo cuando $2k>n$ .

Está claro que a lo sumo puede existir uno de estos ciclos, podemos seleccionarlo en $\binom{n}{k}\times (k-1)!$ formas y luego permutar los elementos restantes en $(n-k)!$ formas.

---

También observamos que la probabilidad a $51,52,\dots$ o $100$ -el ciclo existe es sólo la suma individual de probabilidades ya que estos eventos son independientes.

---

Por lo tanto la probabilidad de que los prisioneros fallen es:

$$\sum\limits_{k=51}^{100} \frac{\frac{100!(k-1)!(100-k)!}{k!(100-k)!}}{100!}=\sum\limits_{k=51}^{100} \frac{(k-1)!}{k!}=\sum\limits_{k=51}^{100} \frac{1}{k}\approx 0.688$$

Answer 3

La respuesta de @Acccumulation ya lo menciona, pero creo que necesita más énfasis: dependencia es la clave. Suponiendo que la permutación de los números sea completamente aleatoria, no importa qué mitad de los cajones abra el primer prisionero - mientras sean 50 cajones diferentes (abrir el mismo cajón dos veces es obviamente subóptimo), la probabilidad de encontrar su número es exactamente $1/2$ lo que sea que haga.

La clave está en la dependencia de las elecciones de los presos.

Supongamos que $P(A_i)$ es la probabilidad de que el $i$ 'El prisionero encontró su número. Como hemos observado, $P(A_1) = 1/2$ , pero en realidad $P(A_i) = 1/2$ para cualquier $i$ . Sin embargo, como los prisioneros pueden hacer sus elecciones basándose en la permutación oculta en los cajones, son capaces de forzar $A_i$ y $A_j$ ser dependiente y concentrar los fallos en un conjunto concreto de permutaciones.

Más concretamente,

• considerar el conjunto de todas las permutaciones posibles en los cajones $\Omega = \{\pi_1, \pi_2, \ldots\}$ ,
• llamemos a una permutación $\pi$ con éxito para el $i$ 'el prisionero si su estrategia de búsqueda logra encontrar su número,
• definir $\Omega_k$ como el conjunto de permutaciones que tienen éxito para todos los prisioneros en el rango $\{1,\ldots, k\}$ .

La probabilidad básica nos da $P(A_1) = \frac{|\Omega_1|}{|\Omega|} = \frac{1}{2}$ . Ahora, si el segundo prisionero hiciera sus elecciones al azar, entonces dividiría $\Omega_1$ más a la mitad, es decir, el tamaño de $\Omega_2$ sería la mitad del tamaño de $\Omega_1$ y un cuarto de $\Omega$ . Por otro lado, ajustando su estrategia, es decir, teniendo en cuenta la permutación que observa, el segundo prisionero puede intentar concentrar sus éxitos en las permutaciones en $\Omega_1$ y sus fracasos en las permutaciones en $\Omega \setminus \Omega_1$ . De esta manera $|\Omega_2|$ es estrictamente mayor que $|\Omega| / 4$ aunque más pequeño que $|\Omega_1|$ . Si todos los presos siguen el ejemplo, cuando uno fracasa, muchos otros también fracasarán, pero también cuando uno tiene éxito, muchos otros también lo tendrán.

Por último, para intuir por qué los cajones particulares abiertos no importan mucho (es decir, por qué importa menos que la dependencia): supongamos que hacemos que los prisioneros se pongan de acuerdo en un arbitrario permutación $\sigma$ y seguir una estrategia en la que el $i$ El prisionero comienza con $\sigma(i)$ y cuando encuentre $x$ en el cajón, sigue con $\sigma(x)$ . Esta estrategia no cambia nada en las probabilidades - porque la permutación $\pi$ en los cajones es aleatoria, la probabilidad de $\pi \circ \sigma$ que tiene un ciclo de longitud $\geq 51$ también es menor que $70\%$ . Aunque ningún preso puede comprometerse de antemano con un conjunto de cajones para abrir, los cajones abiertos son, debido a $\sigma$ En cierto modo, arbitrario.

Rompecabezas de bonificación:

Hay otro rompecabezas que utiliza una técnica similar. Hay 100 prisioneros que llevan sombreros, negros o blancos (asignación arbitraria, no hay restricciones de conteo). Todos se ven entre sí, pero no el color de sus sombreros. Cada uno de ellos escribe en un papel (para que los demás no lo vean) qué color de sombrero cree que tiene. Si todos han acertado, son libres. ¿Cuál es la mejor estrategia para que los prisioneros adivinen el color de sus sombreros?

Espero que esto ayude $\ddot\smile$