Imagen de Rezuanur Rahman Mubin extraída de Unsplash
El Acertijo del Puente y la Linterna (Bridge and Torch Problem) es un clásico problema de lógica que se hizo muy popular en los procesos de selección de empresas tecnológicas como Microsoft o Google.
La trampa intuitiva del problema radica en asumir que la persona más rápida siempre debe actuar como el “taxista” del grupo, acompañando a los demás y volviendo con la linterna. Sin embargo, cuando las diferencias de velocidad entre los integrantes son grandes, esta estrategia no es óptima.
Imagina que cuatro personas (A, B, C y D) se encuentran en la orilla izquierda de un río por la noche y necesitan cruzar al otro lado a través de un puente estrecho y peligroso. Las reglas del cruce son las siguientes:
Velocidades individuales: Cada persona tarda un tiempo distinto en cruzar el puente completo:
Persona A: 1 minuto.
Persona B: 2 minutos.
Persona C: 5 minutos.
Persona D: 10 minutos.
Capacidad del puente: El puente sólo puede soportar como máximo a dos personas al mismo tiempo.
Uso de la linterna: Es de noche y disponen de una única linterna compartida. Para cruzar de forma segura en cualquier dirección, el grupo que cruza debe llevar siempre la linterna.
Ritmo de marcha: Cuando dos personas cruzan juntas, avanzan al ritmo de la persona más lenta del par.
La pregunta decisiva que debemos responder es: ¿Cuál es el tiempo mínimo total necesario para que las cuatro personas crucen al otro lado?
¿Te animas a resolverlo de forma lógica antes de enfrentarte a su modelización?
Solución del reto
Resolviendo el modelo de optimización lineal entera mixta se obtiene el siguiente plan de viajes óptimo:
Viaje
Dirección
Personas que cruzan
Tiempo del viaje
Tiempo acumulado
Viaje 1
Ida (Izq $\rightarrow$ Der)
Personas A y B
2 min
2 min
Viaje 2
Vuelta (Der $\rightarrow$ Izq)
Persona A
1 min
3 min
Viaje 3
Ida (Izq $\rightarrow$ Der)
Personas C y D
10 min
13 min
Viaje 4
Vuelta (Der $\rightarrow$ Izq)
Persona B
2 min
15 min
Viaje 5
Ida (Izq $\rightarrow$ Der)
Personas A y B
2 min
17 min
Resultado: El tiempo mínimo total necesario para que las 4 personas crucen el puente es de 17 minutos.
La clave estratégica radica en el Viaje 3: al hacer que las dos personas más lentas (C y D) crucen juntas, absorbemos el tiempo de C (5 min) dentro de los 10 minutos de D, ahorrando un tiempo valioso.
Este acertijo se puede formular de forma automática y sistemática como un modelo de Optimización Lineal Entera Mixta. ¿Te atreves a intentarlo?
Para resolver el problema de cruzar el puente de forma sistemática, calculamos en primer lugar el número de trayectos necesarios. Para $N=4$ personas, se requieren $T = 2N - 3 = 5$ viajes (3 viajes de ida y 2 de vuelta para retornar la linterna).
Conjuntos de índices
\(\mathcal{P} = \{\text{A}, \text{B}, \text{C}, \text{D}\}\): Conjunto de personas.
\(\mathcal{T} = \{1, 2, 3, 4, 5\}\): Conjunto de viajes. Los viajes impares ($t \in {1, 3, 5}$) son de ida (izquierda a derecha) y los pares ($t \in {2, 4}$) son de vuelta (derecha a izquierda).
Parámetros
\(c_p\): Tiempo necesario para que la persona $p \in \mathcal{P}$ cruce el puente ($c_A=1$, $c_B=2$, $c_C=5$, $c_D=10$).
Variables de decisión
\(x_{pt} = 1\) si la persona $p \in \mathcal{P}$ cruza el puente en el viaje $t \in \mathcal{T}$, y $0$ en caso contrario.
\(y_{pt} = 1\) si la persona $p \in \mathcal{P}$ se encuentra en el lado de destino (derecha) tras finalizar el viaje $t \in \mathcal{T}$, y $0$ en caso contrario (con $y_{p0} = 0 \; \forall p \in \mathcal{P}$).
\(w_t \geqslant 0\): Duración del viaje $t \in \mathcal{T}$.
El objetivo es minimizar el tiempo total acumulado de todos los viajes:
Función objetivo
\[\min z = \sum_{t \in \mathcal{T}} w_t\]
Definimos la lógica del movimiento como restricciones lineales:
Capacidad del puente y retorno de la linterna:
En los viajes de ida (\(t \in \{1, 3, 5\}\)) deben cruzar entre 1 y 2 personas:
Sólo pueden cruzar a la derecha las personas situadas en la orilla izquierda ($y_{p,t-1}=0$):
\[x_{pt} \leqslant 1 - y_{p,t-1} \quad \forall p \in \mathcal{P}, \; \forall t \in \{1, 3, 5\}\]
Sólo pueden regresar a la izquierda las personas situadas en la orilla derecha ($y_{p,t-1}=1$):
\[x_{pt} \leqslant y_{p,t-1} \quad \forall p \in \mathcal{P}, \; \forall t \in \{2, 4\}\]
Actualización del estado de posición:
\[y_{pt} = y_{p,t-1} + x_{pt} \quad \forall p \in \mathcal{P}, \; \forall t \in \{1, 3, 5\}\] \[y_{pt} = y_{p,t-1} - x_{pt} \quad \forall p \in \mathcal{P}, \; \forall t \in \{2, 4\}\]
Condición final:
Al terminar el último viaje ($t=5$), todas las personas deben estar en el lado derecho:
\[y_{p5} = 1 \quad \forall p \in \mathcal{P}\]
Duración del viaje (ritmo del más lento):
El tiempo del viaje $t$ viene acotado por la persona más lenta de entre las que cruzan:
\[w_t \geqslant c_p x_{pt} \quad \forall p \in \mathcal{P}, \; \forall t \in \mathcal{T}\]
Dominio de las variables
\[x_{pt}, y_{pt} \in \{0, 1\} \quad \forall p \in \mathcal{P}, \; t \in \mathcal{T}\] \[w_t \geqslant 0 \quad \forall t \in \mathcal{T}\]
Código fuente
La implementación en Python utilizando la librería Gurobipy para resolver este problema de optimización se encuentra disponible en el repositorio de GitHub.
¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.
Si encontró esto útil, puede citarlo como:
Martín-Campo, F. Javier (May 2026). Cruzando el puente de noche. https://www.fjmartincampo.com/blog/2026/bridgecrossing/.
o en formato BibTeX:
@misc{martín-campo2026cruzando-el-puente-de-noche,title={Cruzando el puente de noche},author={Martín-Campo, F. Javier},year={2026},month={May},url={https://www.fjmartincampo.com/blog/2026/bridgecrossing/}}
Le gustó leer este artículo?
Aqui están algunos artículos relacionados que le pueden gustar:
