El dilema de los Panamericanos: 1355 llaves para 1355 puertas
A Carl Friedrich Gauss (1777-1855), uno de los matemáticos más grandes de la historia, le decían el Princeps Mathematicorum, el príncipe de los matemáticos. El apodo no era antojadizo: cuenta la leyenda que a los 7 años su profesor, aburrido de que el pequeño Carl no pusiera atención en clases, lo castigó igual que a Bart Simpson: se tenía que quedar después de clases sumando todos los números del 1 al 100.
El profesor tampoco era tonto: sabía que le iba a tomar harto tiempo. Eran varias sumas, que en total daban 5050.
Se debe haber caído de espaldas cuando Gauss se le apareció cinco minutos después con la respuesta.
En ese tiempo no existían las calculadoras científicas, así que le pidió que explicara su procedimiento. El niño Gauss no se hizo de rogar: encontró que había un patrón cuando sumaba el primer número con el último (1+100), el segundo número con el penúltimo (99+2) y así sucesivamente... Siempre el resultado era 101.
Y si estimaba cuántas veces obtendría el número 101, llegó a la conclusión de que serían 50 (porque está sumando parejas). ¿La solución entonces? 50 *101 = 5050. Si te perdiste, este tiktok lo deja clarísimo.
Otra forma de resolver el problema sería poner en una fila todos los números del 1 al 100. Abajo, en una segunda fila, los del 100 al 1, y sumar los de arriba con los de abajo.
La solución queda a la vista. En la tercera fila hay 100 veces el número 101. Podemos multiplicar eso, pero sabemos que la suma del 1 al 100 está duplicada en este ejercicio (a diferencia de la manera anterior de resolverlo, podemos ver que al principio se suma 1+100 y al final se vuelve a hacer la misma suma, 100+1). Por eso se hace necesario dividir por dos.
$$=\frac{{(100)}*{(101)}}{2}$$
Gracias a Gauss, este tipo de problema se puede resolver rápido con una fórmula bien elegante: n(n+1)/2.
Más de 200 años después del drop the mic que le hizo Gauss a su profe, la organización de los juegos panamericanos mandó a hacer más de 1.300 llaves para los departamentos en que vivirán los atletas durante los juegos. Pero no venían identificadas. Había que probar una por una.
Este problema tiene una forma de resolución matemática similar al que encontró el niño Gauss a los 7 años (al menos en el peor de los casos, cuando nadie tiene la suerte de abrir rápido al probar las llaves).
¿Y cuál sería esa forma de resolver este problema? ¿Existirá una forma más ingeniosa o eficiente de resolverlo desde las matemáticas? Le preguntamos a nuestros lectores y nos llegaron más de 50 respuestas, varias de ellas bien geniales.
Bastián Abad explica con mucha claridad cuál es la forma más ineficiente y bruta de probar las llaves, la que requeriría la mayor cantidad de intentos y llevaría a cabo todas las combinaciones posibles.
Estamos hablando de 1355! (o 1355 factorial): para llegar a esa cantidad absurda de grande de intentos, Abad dice que habría que “mandar a 1355 personas que prueben independientemente las 1355 llaves; si no les sirven, las llaves se revuelven y se reparten de nuevo. Es como barajar un naipe inglés (52! posibilidades)”.
Pero además de ser un número gigante con más de 3000 dígitos (lo puedes calcular en esta calculadora para números grandes), el tema es que si dimensionamos ese número en la realidad, no cabe en el mundo humano. Es más, ni siquiera 52! cabe en un mundo humano.
Las probabilidades de etiquetar un protón o neutrón específico, tirarlo al azar en el planeta tierra y encontrarlo, es más alta que barajar cartas y lograr que coincida con un orden predeterminado. Y es mucho más alta que barajar las llaves de la villa olímpica y dar con la combinación correcta de las puertas.
Recomendamos ver este video para dimensionarlo:
Entonces, ¿cuál es la cantidad de combinaciones necesarias (y no ineficientes) para poder abrir las puertas? Esta es la respuesta en un mundo donde existe la Ley de Murphy (gracias fherrera por darnos la idea de referirnos así a este escenario): en la primera puerta probamos una por una las llaves, y por culpa de Murphy tenemos la mala suerte de que la última llave es la que abre la puerta. Eso quiere decir que metimos las 1355 llaves hasta abrir la puerta.
En la segunda puerta me quedan 1354 llaves porque ya una llave abrió la primera puerta, y si sigo con la Ley de Murphy, hago 1354 intentos hasta abrir la puerta en la última llave. En la tercera, son 1353 intentos… ¿Les suena 1355+1354+1353 hasta 1? Es el mismo problema que le puso el profesor a Gauss de sumar los números del 1 al 100, pero acá son del 1 al 1355.
Carlos Ortega, una de las cartas ganadoras, lo explica con mucha claridad y tuvo la deferencia de citarlo a Gauss.
Respuesta Carlos Ortega
La primera parte del problema es sencilla: la cantidad de combinaciones (es decir, la cantidad máxima de pruebas que serían necesarias para identificar todas las llaves) sería la suma de los intentos individuales, que se distribuyen de la siguiente manera: 1355 intentos para la primera llave, 1354 intentos para la segunda, 1353 para la tercera, y así sucesivamente hasta 1 para la última. Lo interesante es que existe una forma elegante de resolver esta suma (una formulación que no es mía, sino que nos dejó quien probablemente haya sido el genio más grande de las matemáticas, Carl Friedrich Gauss): la idea fundamental es que, al sumar el primer número con el último, luego el segundo con el penúltimo, y así sucesivamente, el resultado siempre es constante:
1 + 1.355 = 1.356
2 + 1.354 = 1.356
3 + 1.353 = 1.356
...y así sucesivamente.
Siguiendo esta lógica, la suma se puede expresar de dos formas equivalentes:
Sn = 1 + 2 + 3 + ... + n, o también
Sn = n + (n-1) + (n-2) + (n-3) + ... + 1
Si sumamos ambas formas de resolver la suma término a término, obtenemos:
2Sn = (n+1) + (n-1+2) + (n-2+3) + ... + (n-1354+1355)
Simplificando esta expresión, llegamos a:
2Sn = (n+1) + (n+1) + (n+1) + ... + (n+1), y donde la cantidad de
sumandos (n+1) es, precisamente, n.
Finalmente, podemos escribir la fórmula general para la suma aritmética:
Sn = n * (n+1) / 2
Aplicando esto al caso específico de 1355:
Sn = 1355 * (1355 + 1) / 2
Sn = 918.690
En resumen, Ortega nos mandó la fórmula n * (n+1) / 2, que sería 1355* (1355+1)/2. Pero termina la carta con algo que no hemos visto con Gauss y que nos acerca más aún a la realidad, y nos aleja de la tiránica Ley de Murphy:
Carlos dice: “el número máximo de pruebas llave-cilindro sería de 918.690, asumiendo que cada llave abre siempre la última puerta probada. No obstante, según la probabilidad y la estadística, sabemos que la probabilidad de que esto ocurra (es decir, que siempre se deba llegar hasta la última puerta sin probar para abrirla) es casi cero. Por lo tanto, el número real de pruebas debería estar cerca de la semisuma entre la cantidad mínima (1355) y máxima (918.690) de pruebas, alrededor de 460023”.
Ese número “real” que menciona Carlos es el escenario esperado. Interpretamos que Carlos llegó a ese número con la siguiente lógica:
- En el mejor de los casos, si se tiene mucha suerte y se resuelve el problema achuntándole a la primera a la puerta con la llave correcta, solo habría que probar llaves 1355 veces (una llave por cada puerta).
- Como ya dijimos, en el peor de los casos, el escenario ley de murphy serían 918.690 intentos.
- Y el promedio entre esos dos podría ser el escenario esperado: (1355+918690)/2 = 460023.
Juan Figueroa y Pedro Bahamondes estimaron ese mismo número de 460.023 intentos para el escenario esperado, pero no solo eso, además calcularon el tiempo que podría tomar cada escenario:
Respuesta de Juan y Pedro
Juan mandó un notable PDF que puedes ver acá.
Esta es la respuesta de Pedro desde que da con el número correcto :
(...) Unas 918690 pruebas. Esto es en el peor de los casos, puesto que para n llaves disponibles, en realidad la esperanza es que la encontremos en (n+1)/2 intentos, lo que se traduciría en un una esperanza de hallar todos los pares en 460022.5 intentos.
Nótese que esos 460023 intentos (por ser pesimistas vamos a redondear para arriba jaja) se obtienen probando en serie, así que no es muy paralelizable. Una única persona tendría que hacer esos 460023 intentos. Si cada prueba toma unos 10 segundos, esa persona se tomaría casi 2 meses en resolver su problema (¡sin comer, dormir o depositar en Fintual!). Una suposición más realista es que asumamos que tenemos M personas encargadas de estar probando llaves (mientras mayor M, más podemos paralelizar). Para efectos del ejemplo, asumamos que M = 5, que es uno de los dos divisores primos de 1355 y por lo tanto nos simplifica algunos cálculos (siempre podemos dejar unas pocas chapas aparte y resolver el problema para un número más grande).
Podemos imaginar las chapas como un arreglo de 1355 elementos.
[chapa_1, chapa_2, chapa_3, chapa_4, chapa_5, chapa_6, ..., chapa_1355]
Cada uno de nuestros trabajadores, podría tomar entonces 1355/5 = 271 llaves y comenzar a probarlas en cada chapa. Para poder mantener la trazabilidad de qué pares se han encontrado, basta con que cada vez que se encuentre un par chapa-llave correcto, se deje la puerta abierta con la llave puesta, para que nadie siga intentando encontrarle llave. La gracia acá es que si un trabajador termina de probar sus 271 llaves y aún no encuentra match, puede pasar a cualquier chapa desocupada. Para no volver a una chapa que ya probó, mi sugerencia es que pase de la chapa_(i) a la chapa_(i+1), y para evitar que se crucen o caminen demasiado, deberían estar lo más separados dentro de lo posible. Vale decir, las secuencias de cada uno se verán algo como:
Trabajador 1: [chapa_1, chapa_2, ..., chapa_1355]
Trabajador 2: [chapa_272, chapa_273, ... chapa_1355, chapa_1, ... chapa_271]...Trabajador 5: [chapa_1085, chapa_1086, ... chapa_1355, chapa_1, ... chapa_1084]
Lamentablemente, esto solo mantiene nuestras probabilidades de match chapa-llave, así que solo lograremos reducir el tiempo por un factor M. Para 5 trabajadores, tendríamos que tenerlos 920045 segundos o cerca de 11 días continuos, o unas 32 jornadas de 8 horas (!) y todo esto siendo bastante optimistas con respecto al tiempo por chapa y a ignorar tiempos de desplazamiento de chapa en chapa.
Por otra parte, si los pares llave-chapa no son perfectos (puede que una llave abra más de una chapa, sin que necesariamente la llave original de la chapa abra las demás chapas), podríamos creer que estamos forzados a probar las 1355² pares llave-chapa (y por lo tanto aproximadamente duplicar el tiempo de pruebas!) y luego tratar de resolver algún sistema de ecuaciones para asignar los pares compatibles, pero suponiendo que son suficientemente escasas las chapas cuyas llaves quedaron asignadas a otras chapas sin tener un reemplazo recíproco, podemos mantener nuestra estrategia original y cambiar las chapas sobrantes en cuestión de horas.
Después de todo, quizás la mejor estrategia es cambiar todas las chapas y marcarlas correctamente esta vez. Aunque fuera media hora por chapa, con 5 cerrajeros el trabajo quedaría terminado en 67.75 horas, o unos 17 días laborales de 8 horas. De paso, pueden poner cerraduras magnéticas y olvidarse del problema de las llaves para la próxima vez que les suceda.
Aunque la lógica para estimar el escenario esperado por Carlos, Juan y Pedro funciona y el resultado es cercano, para calcularlo de forma precisa, la fórmula que se suele usar es la que mandó Rodrigo Cardemil: n(n+1)/4 = 459.345. Estuvieron cerca.
Se divide por 4 porque cuando pruebas llaves una por una, en promedio, los intentos necesarios para llegar al resultado son la mitad.
La coreografía
Ahora démosle la última vuelta de tuerca con una idea que mandaron muchos: ¿se puede hacer más rápido si consigues 1355 voluntarios, cada uno con una llave, que al mismo tiempo intentan abrir una puerta? En palabras de uno de nuestros lectores, Felipe Altamirano: “contraten a 1355 personas y le pasan una llave a cada uno, y van probando abrir la puerta con la llave, si no es, se mueven a la siguiente, el último a la 1ra y así, el tiempo debería disminuir bastante comparado a que solo unas pocas personas prueben todas las llaves”.
Aquí la pregunta es: ¿cuántas veces un grupo de 1355 personas tendría que hacer la coreografía, la coordinación de abrir las puertas al mismo tiempo?¿Cuántos intentos coordinados serían por grupo?
La respuesta, en el escenario de Ley de Murphy, es dividir los 918.690 intentos por los 1355 voluntarios. En el peor de los casos, los esfuerzos coordinados tendrían que ser 678. Se reduce bastante. Y en el escenario esperado serían 339.
Y claro, lo lindo del problema es que no era totalmente abstracto. Así que aquí, además de las mejores respuestas, incluimos algunas más divertidas. Como dijo Harold Mayne-Nicholls, al final problemas de organización como este en un evento tan grande como los panamericanos no son graves: “a la larga, va a generar chistes entre los humoristas, no me cabe ninguna duda”. Bueno, acá tienes varios Harold:
Pueden ver la presentación más grande acá