Nuestra oficina de tarea de rompecabezas el mes pasado fue para salvar un Star Trek grupo de superficie de ocho liderado por el Empresa Oficial de comunicaciones Teniente Uhura (interpretado por el difunto Nichelle Nichols). La tripulación es encarcelada por una raza alienígena, los Catenati, en un planeta en el Collar Nebulosa. Para escapar, tienen que maximizar su probabilidad de realizar una tarea que al principio parece ofrecer sólo una pésima probabilidad de éxito.
Se informa a la tripulación de ocho miembros de la tarea mientras se los retiene temporalmente en una sala común donde tienen libertad para comunicarse y elaborar estrategias. En unas pocas horas, serán conducidos, uno a la vez, a una sala llamada la cámara de la ruleta. Esta sala tiene ocho botones dispuestos en fila, cada uno de los cuales está programado para responder a un miembro de la tripulación diferente. Para engañar a la tripulación, cada botón está mal etiquetado al azar con el nombre de otro miembro de la tripulación. Cada miembro de la tripulación puede presionar hasta cuatro de los botones, en cualquier orden. Cada vez que presionen un botón, verán a quién pertenece realmente el botón. Dentro de sus cuatro intentos, tienen que encontrar el botón que se les asignó. Para que la tripulación salga libre, todos tienen que tener éxito en esta tarea. Si incluso uno de ellos falla, todos serán ejecutados. Después de que un miembro de la tripulación complete su intento, debe ser aislado sin forma de pasar información a ninguno de sus compañeros de tripulación.
Las posibilidades de éxito parecen minúsculas. Si los miembros de la tripulación eligen botones al azar, cada uno tendrá una probabilidad de 1 en 2 de encontrar su botón. La posibilidad de que los ocho tengan éxito es de solo 1 en 256, o alrededor del 0.4 %.
Pero no tienen que presionar botones al azar. Una forma de aumentar la probabilidad de éxito podría ser igualar todas las pulsaciones de botones de alguna manera. Esto nos lleva a nuestra primera pregunta del rompecabezas.
Puzzle 1
¿En cuánto se puede mejorar la probabilidad de supervivencia de la tripulación si se aseguran de que cada botón se presione con la misma frecuencia (en lugar de presionar cuatro botones al azar)?
Rob Corlett y JPayette respondió bien a esto, como lo hicieron con todas las otras preguntas. En cuanto a la escurridiza idea central detrás de los acertijos de esta columna, Rob Corlett, JPayette y Jouni Seppänen lo describió maravillosamente, mientras Sacha Bugnon aportó una solución informática.
Aquí está la respuesta de Rob Corlett:
Una forma de asegurarse de que cada botón se presione la misma cantidad de veces es separar a los prisioneros en dos grupos de 4 del mismo tamaño.
Cada grupo sólo pulsa los botones correspondientes a los miembros de su grupo. Por lo tanto, si A, B, C y D están todos en el mismo subgrupo, solo presionan los botones para A, B, C y D.
Esto cambia el problema para preguntar por la probabilidad de que cada prisionero sea asignado al grupo correcto, ya que entonces se garantiza que presionen su botón en cuatro o menos pulsaciones.
El número de formas de poblar el primer grupo (y por lo tanto también el segundo grupo) con cuatro personas es el número de formas de elegir 4 de 8, que es C(8, 4) = 70. Por lo tanto, el número total de formas de asignar a todos en los dos grupos es 70.
Solo hay una asignación que asigna correctamente a cada prisionero al grupo correcto, por lo que la probabilidad de que todos estén en el grupo correcto y todos los prisioneros sobrevivan es 1/70, que es 3.66 veces mejor que el 1/256 de la estrategia anterior. [Pero aún es muy pequeño: solo un 1.4% de probabilidad].
Puzzle 2
Hay una forma de mejorar las pésimas probabilidades originales más de 90 veces, hasta un 36.5 %, ¡lo que parece milagroso! Esta estrategia implica el uso de bucles o cadenas de conjeturas, de ahí las referencias a la Nebulosa del Collar y Catenati (cadena es cadena en latín). En la forma básica de la estrategia, cada miembro de la tripulación comienza presionando el botón que lleva su nombre, luego pasa al botón que lleva el nombre del miembro de la tripulación al que realmente pertenecía el primer botón, y así sucesivamente, creando una cadena de nombres.
Veamos cómo funciona esto en la práctica. En el diagrama, los botones se muestran con sus etiquetas en blanco. Las letras azules a continuación muestran los verdaderos dueños de los botones. Cuando el primer miembro de la tripulación, A, ingresa a la cámara de la ruleta, presiona primero el botón A. Este es el botón de C, por lo que presiona el botón C a continuación, luego el botón E y finalmente el botón F, que de hecho es el botón de A, por lo que lo ha encontrado con éxito en cuatro intentos. Tenga en cuenta que los botones ACEF forman un bucle cerrado de cuatro botones. Cuando los miembros de la tripulación C, E y F se turnen, también recorrerán el mismo circuito cerrado, comenzando desde sus respectivos lugares, y también encontrarán sus propios botones en cuatro intentos.
Este arreglo también tiene dos bucles más pequeños de dos botones cada uno: BD y GH. Estos cuatro miembros de la tripulación encontrarán sus propios botones en dos intentos. Entonces, con este arreglo, todos los miembros de la tripulación tendrán éxito y se habrán ganado su libertad. Está claro que si el arreglo solo contiene bucles de longitud 4 o menos, todos los miembros de la tripulación tendrán éxito y serán liberados. Si, por otro lado, hay un solo bucle de 5 o más, todos los miembros de la tripulación en ese bucle no podrán encontrar su botón en cuatro intentos y la tripulación será ejecutada. Para encontrar la probabilidad de éxito, podemos encontrar la probabilidad de tener un bucle de 5, 6, 7 u 8, sumarlos y restar esa suma de 1. Esto es más fácil de calcular que al revés porque para ocho botones, solo puede haber un solo bucle que tenga 5, 6, 7 u 8 miembros.
¡Hay 8! diferentes maneras de organizar ocho botones. Pero cuando hacemos bucles, el mismo bucle representa ocho de estos arreglos (ABCDEFGH forma el mismo bucle que BCDEFGHA, que es lo mismo que CDEFGHAB, etc.). Entonces, la probabilidad de tener un bucle de tamaño 8 es (8!/8)/8!, que es simplemente 1/8. De manera similar, la probabilidad de tener un bucle de tamaño 7 es 1/7, de tamaño 6 es 1/6 y de tamaño 5 es 1/5. Por lo tanto, la probabilidad de éxito de nuestra intrépida tripulación es 1 − (1/5 + 1/6 + 1/7 + 1/8), o 36.5%, como se mencionó anteriormente.
La estrategia anterior funciona para cualquier número de presos, y la mejora en las probabilidades sobre el enfoque aleatorio aumenta rápidamente a medida que aumenta ese número. Se trata de siete veces para cuatro prisioneros, 24 veces para seis, 93 veces para ocho y un asombroso (3.8 × 1029)-doblar por 100 prisioneros. La clave para comprender este enorme aumento es que el método vincula el éxito o el fracaso de cada miembro del grupo con el de los demás. En gran medida, todos tienen éxito o fracasan juntos. La probabilidad de éxito del grupo no desciende demasiado de la de una sola persona, cayendo solo del 50% para un solo prisionero al 30.69% a medida que aumenta el número de prisioneros sin límite. Por otro lado, la probabilidad de que tenga éxito un enfoque aleatorio o incluso un enfoque de "pulsaciones uniformes de botones" disminuye rápidamente a muy cerca de cero incluso para un pequeño número de reclusos.
Si la lógica detrás de esta estrategia todavía parece confusa, aquí hay un análisis del problema de los 100 prisioneros en este excelente video de veritasium.
Puzzle 3
Este acertijo trataba sobre la teniente Uhura recordando un juego de la infancia, que era esencialmente el mismo acertijo, pero para seis personas. Como pista, sugerí resolver el problema para cuatro personas. Ahora que tenemos la fórmula, podemos calcular fácilmente las probabilidades.
Para cuatro personas, la probabilidad de que el bucle más largo sea solo 2 o 1 es: 1 − (1/3 + 1/4) o 41.7 % con una ganancia de siete veces sobre la elección aleatoria.
Para seis personas, la probabilidad de que el bucle más largo sea 3, 2 o 1 es: 1 − (1/4 + 1/5 + 1/6) o 38.3 % con una ganancia de más de 24 veces sobre la elección aleatoria.
Puzzle 4
A medida que continúa nuestra historia, resulta que a uno de los Catenati le ha tomado especial aversión el Empresa tripulación y los está monitoreando remotamente. Sospecha que han ideado alguna estrategia efectiva basada en el diagrama de Uhura. Está decidido a frustrar su plan deslizándose en la cámara y cambiando deliberadamente el orden de las etiquetas de los botones antes de que comience la ruleta. ¿Podrá frustrar con éxito el plan? ¿Qué tiene que tener especial cuidado en ocultar el grupo de desembarco?
Muy temprano en la discusión de la estrategia de la tripulación, los ojos de Uhura se entrecerraron de repente. Hizo una señal a su tripulación y pasó a hablar en nicholese, anunciando: “Toda la discusión adicional en nicholese, por favor”. Nicholese era un nuevo idioma que Uhura había inventado al principio de su carrera para este tipo de situación, para eludir el uso de traductores universales. “Debes haber notado que Catenati desconfía”, continuó. “Él podría tratar de sabotearnos, así que necesitamos modificar nuestro plan. Esto es lo que tenemos que hacer…”
Uhura esbozó el nuevo plan hasta que estuvo satisfecha de que todos los miembros de su tripulación lo sabían perfectamente bien. Luego reflexionó, con una mirada perdida en sus ojos: “Nombré a Nicholese en honor a una actriz icónica del siglo XX. Me alegro de haber insistido en que la Flota Estelar lo hiciera estándar en todas nuestras naves”.
Se volvió hacia la tripulación. “Eso es todo, oficiales. ¡Sabes qué hacer!"
No sabemos exactamente qué le dijo Uhura a su equipo. Pero JPayette y Rob Corlett tuvieron una muy buena idea. Aquí está Rob Corlett de nuevo:
Si el malvado Catenati se entera de que están empleando esta estrategia, puede cambiar los nombres que se muestran en la pantalla para asegurarse de que haya un ciclo de más de 4.
Para romper esto, los prisioneros deben aceptar una orden secreta que aleatoriza la secuencia. Lo hacen diciendo algo como “si ves el nombre de Uhura, entonces ve al botón marcado como Chekov. Si ve el nombre de Chekov en la pantalla, vaya al botón marcado como Smith, etc.
De esta manera, el reordenamiento por parte de Catenati no importa, ya que solo funciona si conoces la forma en que la tripulación responderá a los nombres en las pantallas. Sin embargo, deben mantener en secreto cualquier reordenación, de lo contrario, se puede romper nuevamente.
Como vimos, Uhura se aseguró de que el secreto se mantuviera a salvo. Cada miembro de la tripulación solo necesitaba usar la misma orden secreta y asegurarse de que el malvado Catenati no supiera qué era. De hecho, el orden cambiado por el malvado Catenati en realidad aumentó la probabilidad de éxito de la tripulación.
Esto es lo que pasó. Uhura fue la primera en ser llevada a la sala de la ruleta. Presionó tres botones. Ninguno era suyo. ¿Debería estar triste o contenta? Contuvo la respiración y apretó la cuarta. ¡Había encontrado su verdadero botón!
Sabía que todos iban a ser salvados.
Puzzle 5
¿A qué límite se aproxima el porcentaje máximo de éxito a medida que el tamaño del grupo de desembarco aumenta indefinidamente? ¿Puede explicar por qué este método es mucho más eficiente que presionar un botón al azar?
JPayette escribió:
Todo lo anterior se generaliza directamente a una tripulación de 2n cada miembro puede presionar como máximo n botones. Del rompecabezas 2, deducimos que su probabilidad de éxito es
1 − (suma sobre k entre n + 1 y 2n de 1 /k).
La suma se puede comparar con la integral de 1/x durante el intervalo [n, 2n], lo que nos permite probar que como n crece hasta el infinito, la probabilidad anterior disminuye para converger en un asombroso 1 − ln(2) ≈ 30.6 %. [En realidad, 30.69 % con dos decimales.]
Rob Corlet agregó:
Si no conoce la integración, puede obtener rápidamente una respuesta aproximada mediante el cálculo utilizando una hoja de cálculo. Llegué a 0.307 una vez n llegó a alrededor de 750, que tiene una precisión de 3 decimales.
Ya hemos explicado anteriormente por qué funciona este método. Todos los bucles de más de 1 son compartidos por varios miembros de la tripulación. Así que sus éxitos y fracasos están altamente correlacionados. Es una ilustración del principio "Todos para uno y uno para todos". ¡Directamente del manual de la Flota Estelar!
Gracias a todos nuestros colaboradores. JPayette y Rob Corlett enviaron respuestas valiosas que hicieron que esta columna de solución pareciera casi redundante. Por desgracia, debo apegarme a nuestra regla de elegir un ganador por columna de rompecabezas. El premio Insights es para JPayette en reconocimiento a las contribuciones aquí y en el rompecabezas anterior. ¡Felicidades! Rob Corlett, tus contribuciones no serán olvidadas.
¡Nos vemos el próximo mes para conocer nuevas perspectivas!
