¿Conoce el acertijo de los 100 presos? Un resumen por si no lo conocen:
"El dilema de los 100 prisioneros y 100 cajones es un problema en la teoria de la probabilidad y la combinatoria Consiste en que cada uno de 100 prisioneros debe encontrar su número en uno de los 100 cajones para sobrevivir y si alguno no lo encuentra, todos morirán; y, cada prisionero puede abrir sólo 50 cajones y no puede comunicarse con los demás prisioneros, excepto en el debate previo de la estrategia. A primera vista, la situación es desesperada, pero existe una estrategia que ofrece a los cautivos una oportunidad de supervivencia aproximadamente del 30%. El científico en computación danés Peter Bro Miltersen fue el primero en proponer este problema en el 2003." (Wikipedia)
¡Ahora analizemos!
Analizaremos la solucion mas optima a este acertijo.
Analisis 1:
Usaremos el caso tradicional. 100 prisioneros/participantes con sus respectivas cajas, con 50 intentos para encontrar su numero.
Te pregunto ¿Cual es la solucion que propones, se te ocurre algo? bueno...
Si pensamos en tomar aleatoriamente la caja, tenemos un 50% de probabilidad de encontrar el numero correspondiente. Pero... Hay un problema... Son 100 participantes... Cual es la probabilidad de que todos encuntren su caja...
No es 50%, hay que multiplicar 50% (1 sobre 2) por cada participante, la operacion:
Redondeando el resultado, es decir sin decimales solo enteros, es del 0%, ¡Es decir! que practicamente ya perdieron los 100 participantes con el metodo cada uno por su lado.
Analisis 2:
Tomemos nuevamente 100 participantes con 50 intentos.
Ahora que sabemos que escojer las cajas aleatoriamente no funciona. Sorprendentemente hay una solucion que garantiza el 31% para todos los 100 participantes (muchisimo mayor que el analisis anterior).
¿Cual es la solución? Supongamos que somos el numero 32, tenemos que buscar la caja con el numero 32, dentro de ella tal vez no este nuestro numero, entonces tomamos el numero de la caja, por ejemplo es el 2, y repetimos, vamos a la caja 2, tomamos el numero dentro y asi... Eventualmente encontraremos nuestro numero...
Analisis 3:
Para poder entender el metodo de los bucles, usaremos mi programa. Esta vez seran 10 participantes con 5 intentos, para una mas facil visualizacion.
Resultados:
Traduccion:
Resultados:
• Participantes: 10 | Intentos permitidos: 5
• Participantes que encontraron su numero con 5 o menos: 2
• Participantes que no encontraron su numero con 5 o menos: 8
• Porcentaje de aprobacion 20% | Porcentaje de desaprovacion: 80%
En este caso la mayoria no encontro su numero con 5 intentos o antes. Sigamos el proceso correspondiente para encontrar nuestro numero:
Aqui muestra como fueron organizadas aleatoriamente los valores por caja:
Supongamos que somos el numero 6. El proceso:
Caja 6 - valor 9 | Caja 9 - valor 7 | Caja 7 valor 2 | Caja 2 - valor 3 | Caja 3 - valor 1 | Caja 1 - valor 8 | Caja 8 - valor 10 | Caja 10 - valor 6 ¡La encontramos!
Cuantos intentos tuvimos para encontrar nuestro numero: 8 intentos. Esto significa que hay un bucle de 8 pares de numeros, es decir que 8 personas estan en este bucle, y para el caso usamos más de 5 intentos.
Analisis 4:
Entonces... Si hay 100 participantes con 50 intentos, el porcentaje es de 31% de que todos lo encuentren. Les muestro un grafico de las probabilidades:
Muestra que: el 31% de los bucles son de 50 o menos, mientras que el 69% es mas de 50 intentos.
Entonces si subimos los intentos, por ejemplo a 80, tenemos que: el aproximadamente el 71% de los bucles son de 80 o menos intentos, y el 21% son de mas de 80 intentos.
En conclusion, entre mas intentos hay mas probabilidad tienen TODOS los participantes de encontrar su numero. Entonces, para que todos los participantes logren su objetivo depende de que tan largo es el bucle, como vemos en la siguiente imagen:
En la imagen podemos sacar 2 bucles, uno de 7 y otro de 3.
Analisis 5:
30% no parece mucho, ¡Pero!, es mas que el de 2 personas...
Si 2 personas escojen su caja aleatoriamente tienen 50% de probabilidad individual de encontrar su numero. Ahora multipliquemos:
Es decir que 2 participantes que usan el metodo aleatorio tiene 25% de probabilidad de que todos encuentren su numero, es decir, 2 personas tiene menos probabilidad de encontrar su numero que usando el metodo de los bucles, que es de 30%.
Analisis 6:
Pero... Siempre es 31% sin importar la cantidad de participantes, la respuesta corta es si.
Si aumentamos los participantes a 1.000, la probabilidad es de 30.7%. ¿Y de 1'000.000? es aproximadamente de 30.6%... Si calculamos, basicamente sin importar el numero de participantes la probabilidad ronda entre un 30.7%.
En perspectiva. 1'000.000 de participantes tienen mas probabilidad de encontrar todos su numero, que 2 personas buscando aleatoreamente. INCREIBLE ¿no?.
¡Hagamos pruebas!
Las pruebas las haremos en un programa que simula esta situacion y solucion. El programa esta en un repositorio de github hecho por mi.
Prueba 1:
10 participantes 5 intentos:
Resultados: la mayoria no lo logro (70%).
Prueba 2:
10 participantes 8 intentos, es decir 71% de probabilidad de que todos lo logren:
Resultados: todos lo logran. Ya que los bucles son de 8 o menos.
Prueba 3:
100 participantes, 40 intentos, 21% probabilidad de que todos lo logren:
Resultados: un poco mas de la mitad fallo.
Prueba 4:
¡1000 participantes! con 500 intentos...
Resultados: la mayaria no lo logro.
Prueba 5:
¡10.000 participantes con 6000 intentos! El programa ya le cuesta un poco de tiempo, pero lo logra.
Resultados: La mayoria no lo logro.
Enlace del programa:
Bibliografia:
https://es.wikipedia.org/wiki/Problema_de_los_100_prisioneros
https://www.youtube.com/watch?v=ksasmB0YPzw