¿Se puede generalizar el rompecabezas “Cuatro personas con una linterna intentan cruzar un puente”?

Muchas gracias, Roger, por señalar una forma más eficiente que mi solución original. Déjame intentar de nuevo.

Supongamos que tiene [matemáticas] N [/ matemáticas] personas. Si los ordena de modo que [matemática] P_1 [/ matemática] sea el caminante más rápido (es decir, tenga el menor tiempo para cruzar el puente), [matemática] P_2 [/ matemática] es el segundo caminante más rápido y así sucesivamente hasta [matemática] P_N [/ math] es el caminante más lento. La estrategia dependerá de si es más rápido para [matemáticas] P_1 [/ matemáticas] viajar con cada persona y regresar solo (esto es cierto si [matemáticas] P_1 [/ matemáticas] es mucho más rápido que todos los demás, lo que lo comprobaremos más adelante) o si es mejor para [math] P_1 [/ math] compartir los viajes de regreso con [math] P_2 [/ math].

La mejor estrategia es tener

• ¿Cuáles son los descubrimientos matemáticos más interesantes del siglo XXI?
• ¿Por qué el coeficiente de elevación de una superficie aerodinámica aumenta con la inclinación máxima?
• ¿Qué es un flujo compresible e incompresible? ¿Qué es una descripción física en lugar de matemática?
• Cómo dibujar una variedad Calabi-Yau
• ¿Cuál es el valor de [matemáticas] \ frac {x ^ {n} -1} {x-1} [/ matemáticas]?

1. [matemáticas] P_1 [/ matemáticas] y [matemáticas] P_2 [/ matemáticas] (las dos más rápidas) se cruzan juntas
2. [matemáticas] P_1 [/ matemáticas] vuelve al punto de partida
3. Opción A : si [matemática] 2 * P_2 <P_1 + P_ {N-1} [/ matemática], entonces [matemática] P_N [/ matemática] y [matemática] P_ {N-1} [/ matemática] (las dos más lento) cruzar juntos.
4. [matemáticas] P_2 [/ matemáticas] vuelve al punto de partida
5. [matemáticas] P_1 [/ matemáticas] y [matemáticas] P_2 [/ matemáticas] se cruzan
6. Opción B : si [matemática] 2 * P_2> P_1 + P_ {N-1} [/ matemática], entonces [matemática] P_N [/ matemática] y [matemática] P_1 [/ matemática] (la más rápida y la más lenta) se cruzan juntos.
7. [matemáticas] P_1 [/ matemáticas] vuelve al punto de partida
8. [matemáticas] P_ {N-1} [/ matemáticas] y [matemáticas] P_1 [/ matemáticas] se cruzan juntas.

En este punto, ya sea que haya seguido la opción A o la opción B, debe tener las mismas personas al otro lado del puente (Si [matemáticas] 2 * P_2 = P_1 + P_ {N-1} [/ matemáticas], entonces la Opción A o la Opción B dará el mismo resultado). Luego, si se trata de una situación en la que [matemática] N> 4 [/ matemática], tendrá que seguir haciendo este sistema para analizar si es más rápido hacer que [matemática] P_1 [/ matemática] haga dos devoluciones viajes o si debe dividir los viajes de regreso con [matemática] P_2 [/ matemática] (regrese al paso 2 y evalúe la Opción A y la Opción B para obtener [matemática] P_ {N-2} [/ matemática] y [matemática ] P_ {N-3} [/ math] a través del puente). La fórmula que expresa esto va a ser bastante fea, así que no me voy a molestar con eso. Para ilustrar este punto, podemos ver que en el ejemplo dado en esta pregunta, la mejor estrategia es la Opción A:

1. A y B se cruzan (2 minutos)
2. A regresa (1 minuto)
3. C y D se cruzan juntas (10 minutos)
4. B regresa (2 minutos)
5. A y B se cruzan (2 minutos)

que toma 17 minutos (en oposición a la Opción B, que toma 19 minutos). Sin embargo, si cambiamos las velocidades a A = 1 minuto, B = 3 minutos, C = 4 minutos y D = 5 minutos, entonces deberíamos optar por la Opción B:

1. A y B se cruzan (3 minutos)
2. A regresa (1 minuto)
3. A y C se cruzan (4 minutos)
4. A regresa (1 minuto)
5. A y D se cruzan (5 minutos)

que toma 14 minutos (en oposición a la Opción A, que toma 15 minutos).

El único otro punto a resolver es si tienes un número impar de personas cruzando este puente. En este caso, después de pasar por las iteraciones [matemática] (N-3) / 2 [/ matemática], quedará una persona en el primer lado del puente ([matemática] P_3 [/ matemática]), entonces [matemática ] P_1 [/ math] volverá y luego se cruzará con [math] P_3 [/ math].

Respuesta original (incorrecta):
Bueno, típicamente el plan es hacer que la persona más rápida (FP) camine con cada persona y el FP regresará cada vez. Entonces, la solución debería ser:

1. FP y la Persona A cruzan el puente (Tiempo = Tiempo de caminata de la Persona A)
2. FP regresa al punto de partida (Tiempo = tiempo de caminata de FP)
3. FP y la Persona B cruzan el puente (Tiempo = Tiempo de caminata de la Persona B)
4. FP regresa al punto de partida (Tiempo = tiempo de caminata de FP)
5. y así

Esto continuará hasta que todos estén al otro lado. El punto importante es que FP no tendrá que regresar en este punto. Entonces, el número de veces que FP tendrá que regresar será N-2 (N = número de personas) ya que FP no tendrá que regresar por sí mismo y no tendrá que regresar después de la persona final. Entonces la solución general debería ser:

Suma de los tiempos de caminata de todas las personas, EXCEPTO para FP plus [tiempo de caminata para FP] * (N-2)

EDITAR: Entonces, en el ejemplo proporcionado anteriormente, tenemos:
[matemáticas] Tiempo = (10 + 5 + 2) + (1) * (4-2) = 17 + 2 [/ matemáticas]
[matemáticas] Tiempo = 19 minutos [/ matemáticas]

Además, me molesta la sugerencia de que soy un caminante tan lento. Quiero decir, Ann definitivamente puede reservarlo, pero no hay forma de que sea 10 veces más rápido que yo 🙂