Permutaciones y estrategias

Como abrir una caja fuerte

Un equipo de 5 personas deben abrir una caja fuerte cuya clave consta de 5 dígitos comprendidos entre 0 y 9. Cada persona conoce una de las cifras del código, por ejemplo 3, 7, 6, 5 y 2. Cada persona accede a la caja fuerte en ese orden, sin poder comunicar con los demás.

Los dígitos del teclado se han intercambiado de manera aleatoria y cada persona dispone de 5 intentos para dar con la cifra correcta. A la sexta pulsación el sistema de seguridad bloquea el teclado y ya no se puede abrir la caja fuerte.

Si cada persona escogiera las teclas al azar, la probabilidad de pode abrir la caja fuerte sería:
$$(1/2)^5=3,125 \%$$

¡Podemos multiplicar por algo más de diez la probabilidad de éxito!

• Comenzar por la tecla marcada con el dígito deseado.
• Si la cifra que aparece es la correcta, confirmar. Si no, borrar y pulsar la tecla del dígito aparecido.
• Repetir la operación hasta dar con el número correcto o hasta agotar los intentos.

Supongamos que se ha generado, de manera aleatoria, la siguiente permutación:

 Todas las cifras se obtienen a la 5ª pulsación, por ejemplo para el 3, aparecen sucesivamente 6, 9, 5, 8 y 3.

Esto ocurre porque la permutación tiene dos "ciclos" de 5 elementos, el anterior y el formado por 0, 1, 2, 4, 7.

 En cambio si la permutación aleatoria fuera:

habría un ciclo de 9 elementos: 6, 9, 5, 8, 4, 0, 1, 2, 3 y un ciclo de un sólo elemento: 7.
 Por tanto, si el dígito pertenece a un ciclo de más de 5 elementos se pierde.

¿Por qué esta estrategia es la óptima? 

Lógicamente, ninguna permutación puede contener un ciclo de más de 6 elementos. Estas permutaciones, teniendo en cuenta las diferentes ordenaciones que se pueden obtener, para n>5 son:

$$\binom {10} {n}(n-1)!(10-n)!=\frac{10!}{n}$$

Como hay 10! permutaciones de 10 dígitos, la probabilidad de que una de ellas contenga un ciclo de n>5 elementos es 1/n.

Por tanto la probabilidad de abrir la caja fuerte es:
$$1-\frac{1}{6}-\frac{1}{7}-\frac{1}{8}-\frac{1}{9}-\frac{1}{10}\simeq35,4\%$$

Supongamos que 100 prisioneros son llevados a una habitación en la que hay un fichero con 100 cajones, cada uno de los cuales contiene el nombre de cada uno de los reclusos.

Uno por uno, los prisioneros pueden acceder al fichero y abrir hasta un máximo de 50 cajones, para luego dejar todo como estaba. No pueden comunicarse entre si una vez haya empezado el proceso.

Para salir libres, cada recluso deberá encontrar su nombre en alguno de los cajones que abra; si no ocurre, todos serán ejecutados. El carcelero coloca los nombres de manera aleatoria en los cajones para entorpecer el plan de los reclusos.

Este problema es análogo al anterior. Si los reclusos fueran abriendo los cajones al azar, la probabilidad de salvarse sería:
$$(1/2)^{100}$$
Pero si eligen la misma estrategia que en el caso de la caja fuerte, el  número de permutaciones con ciclos con n>50 es:
$$\binom {100} {n}(n-1)!(100-n)!=\frac{100!}{n}$$

Como hay 100! permutaciones de 100 nombres, la probabilidad de que una de ellas contenga un ciclo de n>50 elementos es también 1/n.

Por tanto la probabilidad de salvarse los 100 presos es:
$$1-\frac{1}{51}-\frac{1}{52}...-\frac{1}{100}\simeq31,2\%$$
Si fueran 1000 presos y abrieran hasta 500 cajones, la probabilidad de salvese sería 30,7%.

Se observa que siempre se suman términos consecutivos de la serie armónica. Esta serie es divergente y se puede comparar con la función ln (n), de acuerdo con las expresiones:

$$H_n=\sum_{k=1}^{n}\frac{1}{k}$$ $$\int_1^n\frac{1}{x}dx=ln(n)$$ $$\lim\limits_{n\to\infty}H_n-ln(n)=\gamma\simeq0,58$$ que es la constante de Euler-Mascheroni.

La probabilidad de perder, son sumas de términos de la serie armónica del tipo:
$$\sum_{k=n+1}^{2n}\frac{1}{k}=H_{2n}-H_n$$ $$\lim\limits_{n\to\infty}H_{2n}-\lim\limits_{n\to\infty}H_{n}=ln(2n)+\gamma-ln(n)-\gamma=ln(2)\simeq0,69314718$$

¡Aunque el número de prisoneros crezca infinitamente, siguiendo la misma estrategia, siempre tendrán una probabilidad de salvarse superior al 30%!

Basado en un artículo de Investigación y Ciencia de Gabriel Uzquiano