El desafío matemático de los 100 prisioneros que nos planteó Héctor Pastén

Este desafío matemático del profesor que ofrece más vacaciones de invierno a sus alumnos, si logran resolverlo,  es en realidad…

El famoso desafío de los 100 prisioneros. Uno de nuestros lectores, Jorge Sánchez , lo adivinó rápido con el correo más corto y preciso que recibimos. Esto fue lo que escribió:

“Pensar que en lugar de 60 cajas son 100.... Luego ver este vídeo.

Saludos".

No era tan difícil de desenmascarar que disfrazamos a los prisioneros de escolares: llevamos al menos 50 años comparando el colegio con la cárcel (una comparación que puso de moda Michel Foucault con su libro Vigilar y Castigar en 1975, y un poco antes Ernie Bushmiller con su cómic Nancy, cuando ilustró perfectamente esa “sensación” del colegio como prisión).

Pero volvamos con el desafío. 

La versión más clásica de este problema de los 100 prisioneros, la planteó el matemático Héctor Pastén en nuestro podcast y es la siguiente: 

Y algo curioso, es que entre el momento en que Héctor planteó el desafío y el día en que entregamos los resultados, Héctor se ganó el prestigioso premio Ribenboim, que lo entrega cada dos años la Asociación Canadiense de Teoría de Números. ¿Cuál era la probabilidad de que eso pasara? Es una pregunta retórica, no nos contesten.

Así que para felicitar a Héctor, dejamos las mejores respuestas que nos llegaron al desafío mientras él iba a buscar su premio a Canadá:

La única respuesta correcta al desafío: 

A modo de ingeniería inversa, lo mejor para entender el problema es partir por la solución y “dibujar” un escenario donde podemos saber todos los números que tienen las cajas adentro. Una vez que veamos la respuesta y la comprobemos, se hace mucho más fácil entender por qué soluciona el problema. 

Si cada prisionero decide no hacer una estrategia colaborativa, sino buscar cada uno por su cuenta su número, cada prisionero tiene 50% de probabilidad de encontrar su número en las 50 cajas. 

Y la probabilidad total de que los 100 prisioneros lo encuentren, se saca multiplicando cada probabilidad individual . Eso es (1/2)*(1/2)* (1/2)* …… 100 veces. Es decir (½) ¹⁰⁰ .

Veritasium, el Youtuber que viralizó el problema el 2022 con más de 14 millones de views (y que fue citado por la respuesta concisa que pusimos arriba),  dice que para poner en perspectiva esta probabilidad, dos personas tienen más opciones de elegir el mismo grano de arena de todas las playas y desiertos en la tierra, que los prisioneros de salvarse.

Pero con una estrategia colaborativa de ponerse de acuerdo los prisioneros suben sus probabilidades de salvarse a 0,31 (una probabilidad de 31%) 

Y si entra el profesor/gendarme con la opción de intercambiar dos números de cajas, increíblemente la posibilidad de que todos encuentren su número revisando máximo 50 cajas es de 100% 

Es decir, dos cambios no tan grandes y bien específicos, hacen que un problema muy complejo y poco probable de solucionar, pase a tener una respuesta que logra que los prisioneros se salven el 100% de las veces.

La estrategia colaborativa

La estrategia que hacen los prisioneros es que cuando les toque su turno, todos van a abrir las cajas siguiendo la misma regla: el prisionero con el número 1 en su polera, va abrir la caja en la posición número uno. Si no encuentra ahí su número, va a ir a la caja en la posición del número que encontró adentro de esa primera caja. Si es el número 7, va a ir a la 7, y así hasta encontrarlo. Ese recorrido lo llevaría finalmente a la caja en la que empezó (la primera, la de su número), creando una primera cadena o loop.

Lo mismo el prisionero 2, va a partir por la caja 2, hasta encontrar su número y volver a la segunda caja. Es decir, la estrategia es que cada prisionero va a seguir cadenas ordenadas, partiendo por su propio número.

La respuesta más completa que recibimos, la escribió Sebastián González mientras estaba enfermo de rotavirus, y dibujó la respuesta para ayudar a visualizar mucho mejor la estrategia. Para no marear, en vez de 100 o 60 como en nuestro ejemplo usó 10 números (y necesitan encontrar el suyo abriendo máximo 5 cajas). 

El alumno 1 va a la caja 1, luego al encontrar el número 7 adentro, se dirige a la 7, de la 7 pasa a la 3 y así… El recorrido total que hace el primer prisionero es 1 → 7 →  3 → 9 → 5 → 4 → 10 → 8 → 2 → 6 → vuelve a 1. 

Desafortunadamente, en el ejemplo el alumno tiene que abrir 10 cajas para llegar a su número, no 5, así que inmediatamente perderían todos los escolares (porque según el desafío, los alumnos solo ganan si todos encuentran su número revisando la mitad de las cajas disponibles, es decir, 5 cajas).

Por suerte, en esta versión del desafío existe la opción de que un gendarme o profesor revise las cajas antes de que los alumnos las abran, y si ve una cadena más larga que el máximo permitido, puede intercambiar dos números para acortarla.  Lo vamos a explicar con un ejemplo y otro dibujo

Probemos cortando la cadena del primer alumno, que originalmente era de 10, en 2 cadenas de cinco elementos. En ese caso, la idea sería que el alumno en la quinta caja que abre, encuentre el número 1. Como se ve en el dibujos, si seguimos su recorrido, su quinta caja es la que está en la posición 5. Entonces vamos a poner el número 1 en esa quinta caja, y el número 4 que antes estaba en la caja 5, la pondremos en la 6 (donde estaba el 1). Ese sería el intercambio de números que hace el profesor para cortar las cadenas.

No hay que olvidar que la idea de hacer este intercambio es que todas las cadenas o loops de los alumnos queden de 5 cajas o menos. Veamos si resulta

La ruta para los primeros 5 alumnos queda:

* Alumno 1: 1 → 7 → 3 → 9 → 5 (en la cinco encuentra el 1, ahí se cierra el loop)

* Alumno 2: 2 → 6 → 4 → 10 → 8 (en la 8 encuentra la 2)

* Alumno 3: 3 → 9 → 5 → 1 → 7 (en la 7 encuentra la 3)

* Alumno 4: 4 →10 → 8 → 2 → 6  (en la 6 encuentra la 4)

* Alumno 5: 5 → 1 → 7 → 3 → 9 (en la 9 encuentra la 5)...

Hasta ahora, sí, quedan todas las cadenas de los 5 alumnos de 5. ¿Pero por qué? ¿Y qué pasa con el alumno del 6 al 10, se salvan?

Sí, se salvan en todos los casos. Porque quizás lo has intuido: hay algo que se reitera, y es que en los circuitos de arriba hay un patrón.

Hay dos cadenas únicas que tienen el mismo orden pero se repiten, solo que empiezan en distintos puntos. La primera cadena 1, 7, 3, 9, y 5 aparece con los exactos números cuando le toca al alumno 3 y al alumno 5. Los voy a dejar todos juntos para que se vea mejor que los números son los mismos:

Alumno 1: 1 → 7 → 3 → 9 → 5
Alumno 3: 3 → 9 → 5 → 1 → 7
Alumno 5: 5 → 1 → 7 → 3 → 9

Y como dije arriba, incluso tienen el mismo orden, solo que parten en un punto diferente: en el alumno 3 parte en el 3, pero igual que para el alumno 1 y 5, después del 3 siempre viene el 9, y después viene el 5, y así … 

Por su lado, la segunda cadena es 2,6,4,10,8. Estos exactos números le tocan al alumno 2 y al alumno 4, solo que parten en diferentes posiciones.

Alumno 2: 2 → 6 → 4 → 10 → 8
Alumno 4: 4 →10 → 8 → 2 → 6  

Ahora, si queremos saber cómo es el recorrido que hace el alumno 6, miremos esas dos cadenas de arriba el lugar donde está el número 6 y simplemente pongamos todos los números que vienen después:

El recorrido del Alumno 6 es: 6 → 4 → 10 → 8 → 2 (puedes comprobar que está bien mirando el dibujo).

Quizás ahora con los números al frente ya se está haciendo obvio, pero no es fácil verlo si no se escribe: el grupo de alumnos que tienen en sus poleras los números de una cadena específica, todos ellos van a hacer el mismo recorrido de cajas. O sea, todos los alumnos que tienen el número 6, el 4, 10, 8 y 2 en su polera van a abrir las mismas cajas pero empezarán en un punto distinto:

Alumno 6:  6 → 4 → 10 → 8 → 2

Alumno 4:  4 → 10 → 8 → 2 → 6

Alumno 10: 10 → 8 → 2 → 6→ 4 

Alumno 8:  8 → 2 → 6 → 4 → 10

Alumno 2: 2 → 6→ 4 → 10 → 8

Al hacer el mismo recorrido, los cinco alumnos tienen una cadena igual de larga, con la misma cantidad de elementos.  Eso implica que si hay cadenas de 6, los seis alumnos dentro de esa cadena recorren una cadena de seis elementos de largo. Si extrapolamos esto a números más grandes, si existe una cadena de 80 números, 80 alumnos van a tener cadenas con los mismos 80 elementos. Y si el profesor divide la cadena en 2, quedan dos cadenas con 40 elementos, y una posible cadena de un largo máximo de 20 (creada con los 20 alumnos restantes, lo que suma 40 +  40 + 20 = 100 cajas).

Cómo tiene que actuar el profesor, y cómo sabe qué cadena tiene que cortar para que funcione 

Ahora que entendemos los patrones y los ciclos que se repiten, volviendo a nuestro ejemplo de 10, el profesor con un solo intercambio puede cortar cualquier ciclo de 10 en 2, y siempre todos se van a salvar: cinco alumnos van a recorrer máximo un set de cinco cajas y los otros cinco, otro set de cinco cajas distintas.

¿Pero qué pasa con ciclos de distintos largos, que el profesor/gendarme no divide justo en 2? 

La respuesta de Sebastián era 100% correcta, pero al final del correo llega con un nivel de humildad que hace que llegue a tener síndrome del impostor: a pesar de lograr que ganen siempre los alumnos con la solución que plantea, le quedan algunas dudas y eso no tiene nada de raro: aunque el problema tiene una solución sencilla y elegante, lograr llegar a esa solución y entenderla, es tan difícil que las personas que por primera vez plantearon este desafío, no llegaron a la respuesta, se los tuvo que apuntar un colega. Pero sigamos con las dudas de Sebastián, que son las siguientes:

• La estrategia necesita que el ordenamiento genere una sola cadena de largo N. Si esto no es así, no sirve :/
• Creo que el enunciado del problema no es suficiente para resolver todos los casos. Por ejemplo, si justo sale un ordenamiento que tiene 2 o más cadenas de largo 2, con un solo movimiento no va a poder generar 2 cadenas de largo N/2.

Pero Sebastián estaba siendo muy autoexigente, porque su solución sí sirve, aunque las cadenas no queden de un largo de N/2. Hagamos un experimento donde la primera cadena solo tiene dos elementos y el profesor aún no ha intervenido:

Acá el alumno 1 encontraría en la primera caja el número 2, y luego va a la caja 2 y encuentra su número. Fin.

El alumno 2 tiene el mismo ciclo: en la caja 2 encuentra el número 1, y en la caja 1, encuentra el suyo (el 2). Esto quiere decir que entre todas las cajas, ya no hay más cajas que puedan apuntar a la caja 1 o la dos. Estas dos cajas se excluyen de los ciclos que quedan, así que de las cadenas restantes el máximo largo posible que puede tener una cadena es de ocho elementos. 

Es decir,  si el profesor encuentra una cadena de números menos de 5, sabe que eventualmente puede encontrarse con una más larga de lo permitido, y puede estimar el mayor largo posible restando la primera cadena corta del total: 10 - 2 = 8.

Esa cadena restante, la podría dividir en 2, y hacer que todos los alumnos ganen por revisar menos de 5 cajas.

Ahora, si después de descubrir la cadena única de 2 elementos, el profesor efectivamente se encontrara con una de 8, para salvar a los alumnos ni siquiera es necesario dividir la cadena en la mitad (que queden 2 cadenas de 4). Podría ser más veloz y eficiente aún, y hacer el intercambio para que el tercer prisionero encuentre su número después de abrir solo tres cajas. Así tendremos dos ciclos: el primero que ya vimos de dos elementos (1,2) y el segundo de tres, por ejemplo con los números (3,4,5). En total, esas son 5 cajas que ya no se van a tener que abrir en las siguientes cadenas, lo que son noticias para celebrar las vacaciones extras: quiere decir que la cadena restante más larga posible sería de 10 - 5 = 5, justo los elementos que no sobrepasan el máximo y asegura que todos ganan. Veámoslo para estar seguros.

Para lograr eso, lo que el profesor quiere es que el alumno número 3 cuando abre su tercera caja (la que está en la posición 5)  encuentre su propio número.Eso quiere decir que el profesor tiene que sacar el 3 que estaba en la 10, ponerlo en la caja 5 donde estaba el 6, y el 6 cambiarlo a la 10. 

Así quedaría con el intercambio

Alumno 3: 3 → 4 → 5 

Eso implica que alumno 4 y 5 también están en la misma cadena

Alumno 4: 4 → 5 → 3 

Alumno 5: 5 → 3 → 4 

Y sobra una cadena de cinco, donde están los alumnos del 6 al 10:

Alumno 6: 6 → 7 → 8 → 9 → 10

Alumno 7: 7 → 8 → 9 → 10 → 6

Alumno 8: 8 → 9 → 10 → 6 → 7

Alumno 9:  9 → 10 → 6 → 7 → 8

Alumno 10:  10 → 6 → 7 → 8 → 9

En conclusión Sebastían,, sin importar el distinto tamaño de las cadenas o que haya más de una, con un solo cambalache o enroque del profesor, todos siempre se salvan. Aunque no te diste cuenta, siempre estuviste en lo correcto

El origen del problema y la matemática detrás: un paper en ciencia de la computación

Este problema apareció por primera vez en un paper de ciencia de computación escrito por Anna Gal y Peter Bro Miltersen el 2003 y no se mencionan prisioneros. El juego está dentro un teorema que ni el autor del paper puede resolver, y deja la pregunta abierta para que otros lo resuelvan. 

En el paper, el juego planteado (que luego se transformaría en el problema de los prisioneros)  es análogo al desafío de recuperar información eficientemente de una estructura de datos: por ejemplo, ir a buscar pedazos de textos específicos en un texto más grande. Ahí, la estrategia de los prisioneros representa ir a buscar los datos (la búsqueda de su número) y la disposición de las cajas, el almacenamiento de esos datos. Los prisioneros logran no tener que pasar por todas las cajas (es decir, no tener que recorrer todos los datos almacenados) para recuperar la información que buscan, y se vuelven más eficientes. 

Bonus: ¿Qué pasa si no hay profesor o gendarme que intervenga? Así era el problema original, y esta es la matemática para llegar a la solución óptima

En su video de Youtube que hizo que este problema se hiciera viral, Veritasium explica lo de los ciclos de la siguiente manera, muy parecido a lo que vimos arriba pero con matemática un poco más sofisticada y números más grandes:

A primera vista, si cada uno de los prisioneros tiene que revisar las cajas por separado sin poder comunicarse con los demás (es decir, sin saber si otro prisionero ha encontrado su número, similar a tratar de encontrar un naipe en un mazo que se baraja cada vez que se vuelve a buscar), el total de posibles combinaciones de cómo los prisioneros pueden revisar las cajas sería 100! (cien factorial).

Pero recordemos que con la estrategia, los prisioneros revisan en loops o cadenas: cada prisionero parte por la caja del número de su polera hasta encontrar su número que lo llevaría a la caja en la que partió. 

Como vimos al principio, existen cadenas que parten distinto y están ordenadas de forma diferente, pero tienen exactamente los mismos números.  El canal de Veritasium muestra este fenómeno de una forma diferente a la nuestra, con un ejemplo que sirve de apoyo para apreciar con más claridad aún las cadenas que se repiten:

1,2,3…97,98,99,100

2,3,4...98,99,100,1

3,4,5…99,100, 1001, 2.. hasta 100:

100, 1,2…97, 98, 99

Estas 100 posibles combinaciones en realidad son el mismo loop, o en otras palabras, todas estas cadenas, del largo de 100 elementos, son una sola. Como existen cien cadenas que se repiten cuando los prisioneros usan esta estrategia de loops, se puede concluir que la cantidad de cadenas únicas del largo de 100 es menor que 100! 

Para ser exactos, la cantidad de cadenas únicas en este caso es  = 100!/100  (se divide por 100 porque son 100 las que se repiten).

¿Por qué queremos saber la cantidad de loops únicos? Porque estamos buscando dentro de esas cadenas, cuál es la probabilidad que alguna de ellas sea más larga que de 50 cajas. Dado que el resto de las cadenas son todas repeticiones, bastará saber solo si alguna de las cadenas únicas se pasa del largo para calcular cuáles son las opciones de que los prisioneros fracasen.

El video muestra que lo más sencillo para hacer el cálculo es primero sacar cuál es la probabilidad de que una cadena única sea del largo de 100. Y solo después calcular cuál es la probabilidad de que una cadena sea del largo de 99… luego de 98, y así hasta 51. Sumando esos resultados, vamos a saber cuáles son las probabilidades de que aparezca una cadena de un largo de más de 50.

Ahora, la fórmula para calcular cuál es la probabilidad de que una cadena única sea del largo de 100 es P(L=100) = número de cadenas únicas del largo de cien elementos/ todas las posibles cadenas.

Arriba calculamos que el número de cadenas únicas del largo de 100 es = 100!/100 y el número de todas las posibles cadenas es 100!. Entonces la probabilidad es (100!/100)/100! = 1/100 

Y para saber la probabilidad de una cadena única de 99 es lo mismo: (100!/99)/100! = 1/99 

Para 98 es 1/98. Por lo tanto, la probabilidad de tener una cadena más larga que de 50 es 🥁🥁🥁: 

1/51 + 1/52 + 1/53… + 1/98 + 1/99 +1/100 = 0,688... Hay una probabilidad de 69% que los prisioneros fracasen por toparse con cadenas de más de 50 elementos y 31% de que tengan éxito, sin la intervención del profesor.

¿Y para el caso de los 60 alumnos, nuestra propia versión del desafío? Es lo mismo, solo que la probabilidad de fracasar baja un poco cuando el grupo es más chico:

1/31 + 1/32+ 1/33… +1/60 = 0.685. Una probabilidad de 68,5% de fracasar y 31,5% de ganar (un poco más alta que con 100 prisioneros).

Analizando el desafío en este nivel de detalle, solo quiero decir que el hecho de que se haya  llegado a estas soluciones así de precisas y sencillas a partir de un problema tan enredado con bajísimas posibilidades de ser resuelto, es impactante: con solo dos “jugadas”, de hacer cadenas y de intercambiar 2 números, un problema estocástico pasa a ser determinista, como dijo Héctor cuando planteó el desafío.

Las respuestas más creativas que recibimos

Además de las respuestas de Sergio y que ya mostramos queremos hacer una mención honrosa a las siguientes respuestas.

Estas dos primeras delatan que faltó un poco de detalle en la explicación que dimos del problema: deberíamos haber dicho que los prisioneros tienen que entrar uno por uno, y ningún prisionero puede hablar o comunicarse con otros durante el desafío, y no puede avisar ni dar pistas de si encontró su número, ni donde. Pero gracias a esa ambiguedad aparecieron estas dos propuestas muy distintas y ocurrentes donde nadie hizo la trampa de buscar la solución.

La respuesta que sigue es justo la antítesis de las anteriores y nos sacó una sonrisa por lo directa.

¿Qué te pareció el desafío, pudiste entenderlo? Si tienes dudas o comentarios del problema o te gustaría plantear otro, escribe a cartas@fintual.com