Las cien cajas numeradas

Hay 100 prisioneros numerados del 1 al 100. En una habitación hay 100 cajas cerradas, también numeradas del 1 al 100.

Dentro de cada caja hay un papel con un número del 1 al 100 (cada número aparece exactamente una vez, distribuido aleatoriamente). Los prisioneros entran uno por uno a la habitación.

Cada uno puede abrir hasta 50 cajas buscando el papel con su número. Si TODOS encuentran su número, todos quedan libres.

Si al menos uno falla, todos mueren. No pueden comunicarse después de entrar a la habitación ni dejar pistas.

¿Existe una estrategia que les dé más del 30% de probabilidad de éxito?

1. Clave: un prisionero acierta si y solo si el ciclo al que pertenece tiene longitud le 50.
2. Como no pueden coexistir dos ciclos >50 en 100 elementos, el evento de fracaso es la unión disjunta: P(fracaso)=sum_ k=51 ^ 100 frac1k.
3. Ese ~31% supera de forma drástica la estrategia aleatoria (2^ -100 para éxito colectivo).

**Respuesta:** SÍ existe una estrategia con ~31% de probabilidad de éxito.

{ width=700px align=center }

**Estrategia de ciclos:**

Cada prisionero abre primero su propia caja y luego sigue la cadena indicada por los números encontrados:

1. Abre caja $i$ (su número).
2. Si dentro está $j$, abre caja $j$.
3. Repite hasta encontrar su número o agotar 50 aperturas.

Los papeles forman una permutación de $\{1,\dots,100\}$, y por tanto una descomposición en ciclos disjuntos.

**Clave:** un prisionero acierta si y solo si el ciclo al que pertenece tiene longitud $\le 50$.

Entonces todos aciertan si y solo si no existe ningún ciclo de longitud mayor que 50.

Como no pueden coexistir dos ciclos $>50$ en 100 elementos, el evento de fracaso es la unión disjunta:
$$
P(\text{fracaso})=\sum_{k=51}^{100}\frac1k.
$$
Por tanto,
$$
P(\text{éxito})=1-\sum_{k=51}^{100}\frac1k\approx 0.31.
$$

Ese ~31% supera de forma drástica la estrategia aleatoria ($2^{-100}$ para éxito colectivo).

---