¿Cómo hacen 100 presos para salir en libertad?
Cuando las matemáticas pueden constituir el mejor plan de fuga
Quiero compartir con usted una historia. En octubre del año 2016, Martín Sombra, un matemático argentino, brillante profesor de la universidad de Barcelona, un gran entusiasta y magnífica persona, me envió un correo electrónico en donde me sugería un problema. Si bien es cierto que ya lo había visto, Martín me propuso que viera una charla TED [1], especialmente dedicada a la educación, en donde se ofrecía una versión ilustrada que resultaba muy atractiva.
Justamente ahora, aprovechando la sugerencia de Martín, quiero escribir sobre el problema que allí se plantea. Verá que, si me acompaña hasta el final, le resultará tan fascinante como a mí. Eso sí, encontrar la solución sin usar alguna de las herramientas que provee la matemática será, no digo que imposible, pero muy difícil de lograr.
Si bien se conocen muchas variantes, la versión original fue planteada por Peter Bro Miltersen, científico danés en el año 2003. Miltersen lo formuló de la siguiente manera:
“El director de una prisión quiere ofrecerles a 100 presos una oportunidad de quedar en libertad. Los reclusos están numerados del 1 al 100. Dentro de una habitación, hay 100 cajones que tienen una etiqueta con números que van del 1 al 100 justamente. El director de la prisión toma 100 papeles y los numera del 1 al 100. Pero en lugar de distribuirlos en forma ordenada, los pone al azar; es decir pone cada papel numerado en cualquier cajón sin necesidad de que los números (del papel y el cajón) sean iguales. Y aquí llega el punto clave.
Inmediatamente después reúne a los 100 presos y les dice que cada uno podrá entrar en la habitación y tendrá que encontrar el cajón donde se encuentra su propio número. Como el director sabe que la probabilidad de encontrar el cajón que contenga el número correspondiente es muy baja, les ofrece una alternativa: cada uno podrá abrir hasta 50 cajones. Si en alguno de ellos encuentra su número, listo. Cierra el cajón y sale sin modificar nada. Deja todo como lo encontró. Las cámaras que están ubicadas en la habitación registrarán lo que sucedió y sabrán si el preso encontró (o no) al abrir a lo sumo 50 cajones, su propio número.
Después de haber entrado a la habitación los 100 presos, si todos encontraron su número, entonces quedarán en libertad. Pero bastará que uno no lo haya logrado, para que el ofrecimiento del director ya no tenga más validez, y cada uno tendrá que cumplir con la condena que tienen establecida.
Los presos pueden debatir previamente alguna estrategia que les parezca adecuada, pero una vez que el primero entra en la habitación, ya no habrá más posibilidades de comunicarse entre ellos.
Pregunta: ¿puede usted elaborar alguna estrategia que les permita tener una ‘buena’ probabilidad de que todos encuentren el cajón con su número?”
Aquí, entonces, una pausa.
Por supuesto siéntase libre de pensar por su cuenta sin necesidad de seguir leyendo lo que escribo más abajo.
Como usted advierte, el problema parece ‘casi’ imposible de solucionar. ¿Por qué? Supongamos que la primera persona entra en la habitación y abriendo un máximo de 50 cajones encuentra su número. Todo bien, pero después, tiene que entrar el segundo preso y también abriendo un máximo de 50 cajones otra vez, tiene que encontrar su número. Y esto no será suficiente para que queden en libertad ni siquiera ellos dos, sino que para que queden en libertad todos… ¡lo mismo tiene que suceder con los 100 presos!
Estaba por escribir que uno tiene que buscar una estrategia, pero aún así: ¿cómo hacer? Es por eso que quiero hacerle una propuesta. En unos pocos renglones quiero escribir algo de matemática que requiere que usted me preste un poco más de atención y verá que después habrá recompensa ‘intelectual’.
Es decir, si usted lee lo que sigue, lo entiende, y puede ‘jugar’ con lo que yo voy a escribir, créame que se sentirá mejor, habrá –eventualmente— inaugurado algunos caminos dentro de su cerebro que no había usado antes (salvo que ya conociera del tema previamente) y quizás podamos entender la estrategia que propuso Miltersen originalmente. Acá voy.
Voy a usar únicamente números naturales: 1, 2, 3, 4, etc.
Si uno toma los dos primeros, 1 y 2, hay dos maneras de ubicarlos en orden:
12 21
Si tomo los tres primeros, 1, 2 y 3, hay seis maneras de ubicarlos en orden:
123 132 213 231 312 321
Si ahora tomamos los primeros cuatro números (1, 2, 3, 4), hay veinticuatro maneras de ordenarlos:
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
Si usted repasa lo que escribí hasta acá verá que:
- Con dos números, hay 2 formas de ordenarlos
- Con tres números, hay 3 x 2 = 6 formas de ordenarlos
- Con cuatro números, hay 4 x 3 x 2 = 24 formas de ordenarlos
Si bien yo no voy a escribir todos los detalles (pero le sugiero fuertemente que lo haga usted), podrá concluir que con los primeros cinco números (1, 2, 3, 4, 5), hay
5 x 4 x 3 x 2 = 120
formas de ordenarlos… y en general, lo mismo sucedería si usted tomara los primeros 100 o 1000 o 100.000 números. Las formas de ordenarlos se calculan multiplicando, por ejemplo:
100 x 99 x 98 x 97 x 96 x 95 x …x 3 x 2 (para los primeros 100)
1000 x 999 x 998 x 997 x 996 x 995 x …x 4 x 3 x 2 (para los primeros 1000), etc.
Cuando uno hace este tipo de multiplicación descendente, empezando en el número 5, el resultado se llama factorial de 5 y se escribe con un número cinco seguido de un signo de admiración: 5! Si usted quiere calcular de cuántas formas se pueden ordenar los primeros 52 números naturales, el resultado es 52! (factorial de 52), o lo que es lo mismo, 52 x 51 x 50 x 49 x 48 x ….x 4 x 3 x 2 … Un número verdaderamente gigantesco [2].
Cada uno de los posibles órdenes, se llama una permutación de esos números. Es decir, (1324) y (4213) son dos posibles permutaciones de los primeros cuatro números naturales, y lo que estuvimos calculando antes es cuántas posibles permutaciones hay entre los primeros 2 ó 3 ó 4 ó 5 ó 100 números naturales.
Como práctica, le propongo que se fije cuán rápido crecen estos números. Es verdaderamente sorprendente, porque mire lo que sucede con el número de permutaciones que se pueden obtener a medida que uno aumenta la cantidad de números.
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Es decir, ¡hay 3.628.800 posibles permutaciones de los diez primeros números naturales! Esto sí que merece signos de admiración.
Una reflexión más. Tomemos una permutación cualquiera de los primeros seis números naturales, digamos 263145. Hagamos de cuenta que cada número está escrito en una bolilla y esta se encuentra dentro de una urna o casillero. Si yo tengo todos los casilleros ordenados, del 1 al 6, correspondería a esta ‘figura’:
1 2 3 4 5 6
2 4 3 1 6 5
O sea, en el casillero número 1 está la bolilla que lleva el número 2, en la segunda casilla está la bolita que lleva el número 4… y así siguiendo. Cada permutación entonces, es un reordenamiento de los seis números.
En este caso, como escribí más arriba, en el primer casillero está el número 2, en el segundo está el número 4, en el tercero sigue el 3, en el cuarto va el número 1, en el quinto casillero está el 6 y en el último el número 5. Pensando cada número como una ‘bolita’ y cada lugar como un casillero, cada permutación equivale a ‘redistribuir’ las bolitas en los casilleros. En el ejemplo que estoy usando, la bolita que lleva el número 3 es la única que se corresponde con el casillero que lleva el mismo número, pero las otras cambian todas de lugar.
Ahora quiero proponerle que hagamos una suerte de ‘viaje’ o ‘recorrido’. Sí, ya sé: no me entiende. Me imagino que usted se debe estar preguntando: ¿viaje? ¿recorrido? ¿De qué me habla? Verá que es muy sencillo.
Empecemos por el primer casillero. Allí encontramos el número 2. Es decir, al abrir el primer cajón, uno se encuentra con la bolilla número 2. Este número 2 nos indica que el próximo cajón o la próxima casilla que uno debe ‘abrir’ o ‘revisar’ es la número 2.
Allí encontramos el número 4. Eso indica que tenemos que ir hasta la casilla número 4. Cuando llegamos allí, nos encontramos con el 1… que, en este caso, coincide exactamente con el lugar (o el número) del que habíamos partido. ¿Me entiende? Es decir, hemos descubierto lo que se llama un ciclo. ¿Por qué? Porque empezando en el 1, pasamos al 2 después al 4 y volvemos al 1. Si lo escribiera usando unas ‘flechas’ para indicar el camino recorrido, sería así:
1 -> 2 -> 4 -> 1.
Ahora empecemos en el 5. Encontraríamos el número 6. Pero al abrir el 6 (o ‘mirar’ lo que hay dentro del casillero número 6), nos encontramos con el 5. ¿Qué indica esto? Que hemos encontrado otro ciclo:
5 -> 6 -> 5 .
En el caso del 3, el ciclo no sale de esa casilla. Es un ciclo particular ya que consiste en un solo elemento. Es un caso particular de ciclo que se llama lazo.
Si usted hace el análisis de todas las posibilidades con esta permutación, descubre que hay únicamente tres ciclos:
(1,2,4), (5,6) y (3).
Como usted advierte, puse entre paréntesis los elementos del ciclo. En el primer caso, el 1 pasa al 2, el 2 al 4 y el 4 vuelve al 1. En el segundo ciclo, el 5 pasa al 6 y el 6 vuelve al 5, y por último, en el caso del ciclo que contiene al 3, uno no sale de ese casillero.
Otra observación: el ciclo (1,2,4) es igual al ciclo (4,1,2) y al ciclo (2,4,1). Es decir, son todos equivalentes porque empezando en cualquiera de los tres casilleros uno hace el mismo recorrido.
Tomemos otro ejemplo, ahora con 10 números. Voy a utilizar esta permutación:
4 3 8 2 6 5 10 1 9 7
Esto correspondería (usando los casilleros y las bolitas) a este reordenamiento:
1 2 3 4 5 6 7 8 9 10
4 3 8 2 6 5 10 1 9 7
Busquemos los ciclos (hágalo usted también, antes de leer lo que voy a escribir acá abajo). Empecemos con el 1.
(1, 4, 2, 3, 8) es un ciclo posible.
Fíjese que tiene longitud cinco (ya que involucra cinco elementos).
Por otro lado, hay tres ciclos más (¿no los quiere buscar usted para ver si está de acuerdo conmigo?)
- (5,6) (que tiene longitud dos),
- (7,10) (que también tiene longitud dos), y por último
- (9), que es un lazo (un ciclo de longitud uno).
Aparecen muchísimas preguntas, y me gustaría estar junto a usted para pensar juntos, pero voy a seleccionar algunas solo para que podamos avanzar, pero el tema es fascinante y se presta para dedicarle un buen rato jugando con las distintas posibilidades e intentando diferentes variantes.
Por ejemplo: en el último caso, de la permutación que elegí (4, 3, 8, 2, 6, 5, 10, 1, 9, 7) pude extraer cuatro ciclos: (1,4,2,3,8), (5,6), (7,10) y (9).
¿Se podrá construir una permutación que tenga un ciclo de cualquier longitud? (Por supuesto, estoy sobreentendiendo que la longitud no puede ser más larga que el número de elementos de la permutación.) Para ponerlo de otra forma: si estoy mirando a las posibles permutaciones de 10 elementos, ¿existen permutaciones que tengan ciclos de longitud 6? ¿De longitud 7 u 8 o incluso 9? ¿Y de longitud 10? (No pregunto sobre otras porque el ejemplo de arriba ya exhibe ciclos de longitudes cinco, dos y uno.)
Contesto yo alguna de las preguntas, pero le propongo que intente usted por su lado. Por caso, si uno tiene esta permutación:
2 3 4 5 6 7 8 9 10 1,
creo que se ve claramente que el único ciclo que uno puede encontrar tiene ¡longitud 10!
¿Se podrá encontrar alguna permutación que tenga un ciclo de longitud 9?
Sí. Este es un ejemplo:
2 3 4 5 6 7 8 9 1 10.
En este caso, el ciclo es (2, 3, 4, 5, 6, 7, 8, 9, 1). Hay otro ciclo, de longitud uno: (10). Como escribí más arriba, todos los ciclos de longitud uno se llaman lazos, ya que como su nombre lo indica, empiezan y terminan en ellos mismos.
En realidad, uno se puede fabricar permutaciones que contengan ciclos de cualquier longitud.
Una última observación (y pregunta): si uno tiene una permutación de los primeros diez naturales, ¿puede haber dos ciclos que tengan longitudes mayores que cinco?
Piénselo usted, pero verá que esto es imposible. Como siempre, leer mi respuesta es como si la (o lo) estuviera engañando, porque… ¿por qué privarse de la oportunidad de pensar si es posible o no? En todo caso, no se robe a usted misma/o la satisfacción de poder deducir ‘algo’ por su cuenta.
De hecho, no puede haber dos ciclos distintos de longitudes mayores que cinco cada uno, porque como en total hay 10 números, tiene que haber por lo menos un número que esté en los dos ciclos, y el ‘recorrido’ que uno debería hacer desde allí, tendría que ser el mismo en los dos casos, y por lo tanto, serían dos ciclos iguales. Dicho de otra forma, cada número forma parte de un único ciclo.
Ahora bien: ¿por qué escribí todo esto sobre las permutaciones y los ciclos? ¿Qué fue lo que me motivó?
¿Se acuerda del problema que planteé al principio? Para que todos los presos queden en libertad, todos tienen que encontrar su número abriendo –a lo sumo— 50 cajones. Pero bastará que uno solo no lo haya logrado, para que el ofrecimiento del director ya no tenga más validez, y de esa forma, cada uno tendrá que cumplir con la condena que tienen establecida.
Los presos pueden debatir previamente alguna estrategia que les parezca adecuada, pero una vez que el primero entra en la habitación, ya no habrá más posibilidades de comunicarse entre ellos.
A diferencia de lo que sucedía cuando empecé esta historia, ahora tenemos la ventaja de conocer lo que son las permutaciones, sabemos calcular cuántas hay (dependiendo del número de objetos a permutar), sabemos lo que son los ciclos (y lazos), y conocemos algunas propiedades.
La pregunta que había planteado entonces era:
“¿Puede usted elaborar alguna estrategia que les permita tener una ‘buena’ probabilidad de que todos encuentren el cajón con su número?”
Antes de avanzar, quiero hacer algunos cálculos con usted, para convencernos de cuán difícil sería lograr el objetivo sin una estrategia. Si cada uno entrara por su cuenta, y al azar abre 50 cajones, ¿cuál será la probabilidad de que los 100 encuentren su número?
Calculémosla juntos.
Fíjese que al entrar el primer preso, la probabilidad que encuentre su número es ½, o lo que es lo mismo, tiene un 50% de posibilidades de encontrarlo. ¿Por qué? Es que como hay 100 cajones y le está permitido abrir la mitad de los cajones, la probabilidad de encontrarlo es ½.
Hasta acá, todo bien. Pero al entrar el segundo preso, la probabilidad de que él encuentre su número, es también ½. Luego, la probabilidad de que los dos encuentren sus respectivos números, se calcula multiplicando las probabilidades, o sea: ½ x ½ = ¼.
Como usted imagina, cada vez que va ingresando un preso, la probabilidad se calcula agregando el factor ½ una vez más. En definitiva, la probabilidad de que todos encuentren su número es:
(1/2)100 = 0, 000 000 000 000 000 000 000 000 000 0008 ….
que es un número muy muy muy pequeño.
Es razonable esperar entonces que los presos se reúnan antes de entrar y piensen alguna estrategia. Cualquiera que encuentren o cualquier plan que decidan seguir, seguramente les dará más posibilidades de salir en libertad que intentar al azar.
Aquí, otra pausa.
Ha llegado el momento en el cual le pido que piense usted alguna estrategia, no importa cuál, pero alguna. Le confieso que yo no tuve oportunidad de pensar nada, porque cuando conocí el problema, un poco antes que me lo enviara Martín, estaba sentado en una cafetería de la Universidad de Chicago, donde un grupo de matemáticos estaban discutiendo… ¡la solución! Como recién me había incorporado a la charla y en la mesa se discutía sobre –justamente— la estrategia que había que elaborar, pregunté cuál era el problema. Lo que sucedió entonces es que yo conocí la solución antes de saber cuál era el problema. Por lo tanto, no puedo escribir acá cuán fácil o difícil me resultó. Pero lo que sí puedo proponerle, como siempre, es que no lea lo que sigue en forma inmediata. Tómese algún tiempo para pensar. No puedo garantizar que se le va a ocurrir lo que se les ocurrió a otras personas, pero tampoco puedo decir que no. Más aún: siendo fiel a lo que pienso, creo que una persona cualquiera, ignorando el grado de dificultad de un problema, tiene muchísimas posibilidades de enfrentarlo y pensar alguna forma de resolverlo totalmente diferente y alejada de lo que estuvieron pensando otros, y eso, en algún sentido, le da una ventaja enorme, ya que no está contaminado al escuchar lo que estuvieron discutiendo otros (u otras), que inexorablemente lo llevan por un camino que ya ha sido recorrido.
Resumen: piense por su cuenta. Quizás llegue usted a la misma conclusión (u otra) por otro camino. ¿Por qué no?
Ahora sí me voy a dedicar a escribir la estrategia, pero lo voy a hacer en un caso más reducido, en donde en lugar de 100 presos, voy a suponer primero que hay solamente cuatro y que se les permite abrir dos cajones.
La estrategia consiste en lo siguiente: el número 1 entra en la habitación y se dirige al cajón que lleva el número 1. Si encontró su número, listo. Cierra el cajón y se retira.
En cambio, si no lo encontró, es porque aparece otro número diferente al 1. En este caso, podría ser 2 ó 3 ó 4. Supongamos que es el número 3. Entonces, con esa información, se dirige al cajón número 3 y lo abre. Si encontró su número, una vez más, se terminó el problema: en dos intentos, encontró el cajón con su número. Cierra el cajón y se retira. En cambio, si no lo encontró, se terminó el problema también, pero lamentablemente perdieron todos, porque estaba claro desde el principio, que cada preso tenía dos chances para encontrarlo.
Para calcular la probabilidad de que todos (en este caso, los cuatro) encuentren su número, voy a analizar todas las posibilidades con las que se puede tropezar cada preso.
Para eso, veamos cuáles son todas las posibles permutaciones de los cuatro números puede haber. Si bien las escribí más arriba, las repito acá:
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
Estas son las 24 permutaciones posibles. Cuando un preso entre en la habitación, se enfrentará con alguna de esas 24 permutaciones. Quiero que analicemos juntos en qué casos encontrará su número y en cuáles no.
En realidad, ¿se acuerda de lo que hice más arriba con los ciclos? Lo que uno tendría que hacer es, una vez que tiene determinada la permutación que eligió el director de la cárcel, fijarse cuántos ciclos hay, y lo que es más importante aún, determinar ¡cuántos ciclos hay de longitudes 3 ó 4! ¿Por qué?
Es que si el preso se encuentra con un ciclo de longitud 3 ó 4, ¡perdió! No va a encontrar su número. En cambio, si encuentra un ciclo de longitud 2 o 1 (un lazo), entonces sí, terminará encontrando su número en dos o menos pasos, que es lo que indica el problema.
Antes de avanzar, quiero hacer una observación más: fíjese que hay ciclos que parecen diferentes pero que son el mismo. ¿A qué me refiero? Como ejemplo, el ciclo (1, 2, 3, 4) es el mismo que (2, 3, 4, 1). O sea, no importa dónde uno empiece; estos dos, si bien parecen distintos, recorren el mismo camino y en el mismo orden. O sea, a los efectos prácticos son indistinguibles.
Busquemos juntos en cuáles permutaciones fallará. Es decir, busquemos las permutaciones que los llevarán al fracaso y contemos cuántas son.
Para empezar, hay seis ciclos de longitud 4:
1 2 3 4 1 3 4 2 1 2 4 3 1 4 2 3 1 3 2 4 1 4 3 2
Después, hay ocho ciclos de longitud 3:
1 2 3 1 2 4 1 3 4 1 4 3
2 3 4 2 4 3 3 2 4 3 4 2
Por lo tanto, de las 24 posibles permutaciones, hay 14 (6 ciclos de longitud 4 y 8 ciclos de longitud 3) que les impedirían (a los presos) encontrar sus números. Si la permutación que eligió el director involucra alguno de estos ciclos, los presos quedarán en prisión y no saldrán en libertad. Sin embargo, las restantes 10 permutaciones resultan tener ciclos de longitud a lo sumo dos (o bien dos o bien lazos). Por lo tanto, como
10/24 = 0.41…
los presos tendrían más de un 41% de posibilidades de encontrar sus números respectivos.
Para completar el caso, escribo acá los 10 que serían exitosas:
(1), (2), (3), (4), (1,2) , (1,3), (1,4), (2,3), (2,4) y (3,4).
En el caso más general, si el número de presos es un número par (digamos 2n), la probabilidad de que encuentren el número se calcula usando esta fórmula:
1 – (1/(n+1) + 1/(n+2) + 1/(n+3) + … + 1/2n)
Por ejemplo, en el caso de 10 presos, resulta ser n = 5.
En ese caso, el resultado es un 35%. Es decir, efectuando el proceso que describí más arriba, en un 35% de los casos, los presos encontrarán la caja que contiene su número. Este número se obtiene haciendo:
1 – (1/6 + 1/7 + 1/8 + 1/9 + 1/10) = 0.35…
De la misma forma, si hubiera 1.000 presos o 1.000.000, la probabilidad se acercaría a un 30%.
Y aquí voy a terminar. No se me escapa que del caso n = 4 al caso general, hay muchísima distancia que yo no puedo cubrir aquí. Hay muchísima literatura escrita al respecto [3], pero esa parte ya se la dejo a usted. Con todo, ¿no es notable que con esta estrategia los presos puedan quedar en libertad en más de un 30% de los casos?
[1] https://www.youtube.com/watch?v=vIdStMTgNl0&feature=youtu.be
[2] Para más información sobre cuán grande es (o son) este (estos) número (s), le propongo que lea la página 106 de Matemática del Futuro, Penguin Random House, publicado en el año 2017.
[3] Le sugiero que lea esta página que publicaron “Los Gaussianos”: https://www.gaussianos.com/solucion-al-problema-de-los-100-presos/
En cuanto a Wikipedia, acá está la versión en inglés con más detalles históricos: https://en.wikipedia.org/wiki/100_prisoners_problem
--------------------------------
Para suscribirte con $ 1000/mes al Cohete hace click aquí
Para suscribirte con $ 2500/mes al Cohete hace click aquí
Para suscribirte con $ 5000/mes al Cohete hace click aquí