Some Generalizations of the Bridge and Torch Problem

Imagina un mundo donde los acertijos más emocionantes no consisten en encontrar un tesoro oculto o resolver un asesinato, sino en lograr que un grupo de amigos cruce un puente oscuro y destartalado antes de que salga el sol. Este es el reino de la optimización combinatoria, una rama de las matemáticas que se pregunta: "¿Cuál es la mejor manera absoluta de hacer algo cuando tienes reglas estrictas?". Piensa en ello como el juego definitivo de Tetris, pero en lugar de bloques, estás encajando personas en franjas horarias, y el objetivo es completar el nivel en el menor tiempo posible. La versión clásica de este juego, conocida como el "Problema del Puente y la Linterna", es famosa por sus reglas engañosamente simples: un grupo de personas debe cruzar un puente de noche con solo una linterna. El puente es estrecho (solo caben dos personas a la vez), la linterna debe ser transportada cada vez que alguien cruza, y si dos personas cruzan juntas, se mueven a la velocidad de la persona más lenta. Parece fácil, pero encontrar el horario más rápido es una danza complicada de tiempos y estrategia que ha desconcertado a muchos.

Ahora, imagina tomar ese mismo acertijo y subir el nivel. ¿Qué pasaría si el puente pudiera albergar a tres personas? ¿O qué pasaría si, en lugar de un solo puente, tuvieras un núcleo con muchos radios, como una telaraña, donde la gente pudiera cruzar a diferentes destinos al mismo tiempo? Eso es exactamente lo que exploraron Thang Pang Ern y Gerard Sayson en su artículo. Tomaron el clásico acertijo del "puente de dos personas", donde todos tienen un tiempo de cruce específico del 1 al $n$, y no solo lo resolvieron; encontraron una fórmula mágica que predice el tiempo mínimo exacto para cualquier número de personas. Luego, llevaron los límites más allá, determinando las reglas para un puente que alberga a tres personas, e incluso para una red en forma de estrella de caminos. Descubrieron que, aunque las respuestas se vuelven complicadas, siguen patrones hermosos y repetitivos que pueden escribirse en una sola ecuación.

La Danza Clásica de Dos Personas

Comencemos con el acertijo original. Tienes un grupo de $n$ personas, y sus tiempos de cruce son simplemente los números $1, 2, 3, \dots, n$. La persona con el tiempo 1 es un velocista, mientras que la persona con el tiempo $n$ es un lento. El objetivo es llevar a todos desde el lado izquierdo del río al lado derecho.

Los autores demostraron que para esta configuración específica, existe una fórmula perfecta de forma cerrada para calcular el tiempo mínimo, $T(n)$. No es solo una suposición; la derivaron descomponiendo el problema en trozos más pequeños. Se dieron cuenta de que la mejor estrategia consiste en enviar a las dos personas más rápidas (1 y 2) primero, hacer que una de ellas regrese con la linterna, enviar a las dos personas más lentas juntas, y luego hacer que la otra persona rápida regrese. Este "bloque" de movimientos despeja a las dos personas más lentas y deja el sistema listo para repetir el proceso para el grupo restante.

Al sumar los costos de estos bloques, encontraron que el tiempo total para $n$ personas es:
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
Esta fórmula funciona para cada número de personas $n$ mayor o igual a 2. También señalaron que la secuencia de tiempos generados (1, 2, 6, 11, ...) es un patrón conocido en el mundo de las matemáticas, pero ellos proporcionaron una prueba directa y fresca de por qué funciona esta fórmula específica. Curiosamente, demostraron que la estrategia "estándar" de simplemente enviar a la persona más rápida de ida y vuelta con todos los demás no siempre es la mejor. Por ejemplo, con 4 personas, la forma estándar tarda más que el ingenioso método de "bloques".

El Puente que Alberga a Tres

A continuación, los autores se preguntaron: "¿Qué pasa si el puente es más ancho?". Imaginaron un puente que puede albergar hasta 3 personas a la vez, pero que sigue teniendo una sola linterna. Esto cambia el juego por completo. Con tres personas, puedes enviar un trío a través, pero aún necesitas a alguien que traiga la luz de vuelta.

Encontraron que para esta versión de "capacidad 3", el tiempo óptimo, $T_3(n)$, sigue un ritmo diferente y más complejo. La fórmula involucra una mezcla de una curva cuadrática (como $n^2/6$) y algunos términos ondulantes de tipo onda que involucran el coseno y $(-1)^n$. Específicamente, para $n \ge 7$, el tiempo es:
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
Esta fórmula es tan única que creó una secuencia de números completamente nueva en la Enciclopedia en Línea de Secuencias de Números Enteros (A392834). Los autores demostraron esto mostrando que la mejor estrategia implica mover grupos de seis personas a la vez en un ciclo específico, reduciendo el problema de $n$ personas a $n-6$ personas con un costo predecible añadido cada vez. También comprobaron números más pequeños (como del 1 al 6) mediante fuerza bruta para asegurarse de que la fórmula encaje con el inicio de la línea.

Mencionaron brevemente un puente que alberga a 4 personas, pero admitieron que el patrón se vuelve desordenado y que aún no han encontrado una fórmula sencilla para eso. Sospechan que existe una fórmula, pero es mucho más difícil de hallar.

La Red en Forma de Estrella

Finalmente, el artículo da un gran salto lejos de un solo puente. Imagina un núcleo central (como una estación de tren) con muchas carreteras (radios) que conducen a diferentes destinos (hojas). Esto se llama un "grafo de estrella". En esta versión, tienes $n$ personas en el centro, $k$ carreteras que salen y $t$ linternas.

Las reglas aquí son un poco diferentes: en un "paso", puedes enviar personas por diferentes carreteras al mismo tiempo, siempre y que nadie use la misma carretera y ninguna persona esté en dos lugares a la vez. El tiempo para ese paso está determinado por la persona más lenta que se mueve en ese paso.

Los autores descubrieron que el tiempo mínimo depende fuertemente de cuántas linternas y carreteras tienes. Si tienes suficientes linternas y carreteras para enviar a todos en un gran estallido, el tiempo es simplemente el tiempo de la persona más lenta ($n$). Pero si estás limitado, el tiempo crece aproximadamente como $n^2$. Derivaron una fórmula de límite inferior:
$$T(n, k, t) \ge sn - ms(s-1)$$
donde $m$ es el menor entre el número de carreteras y linternas, y $s$ es el número de "rondas" necesarias para sacar a todos.

Una de las partes más geniales de esta sección es cómo conecta con las matemáticas puras. Cuando observaron los números generados por este problema de la red en forma de estrella, se dieron cuenta de que estaban recreando identidades matemáticas famosas que involucran la "función suelo" (que simplemente significa redondear hacia abajo al entero más cercano). Por ejemplo, al resolver el acertijo para números específicos de personas y carreteras, "redescubrieron" una identidad conocida sobre la suma de funciones suelo, mostrando cómo un divertido acertijo de programación puede revelar verdades profundas sobre los patrones numéricos.

En resumen, este artículo toma un acertijo clásico, lo resuelve con una fórmula precisa, expande el problema a puentes más anchos y luego lo convierte en una red de múltiples rutas, todo ello mientras descubre la belleza matemática oculta en el camino. Demuestra que incluso en un simple juego de cruzar un puente, existen capas de estrategia y estructura esperando ser descubiertas.