La estrategia del farol

Nuestros cinco intrépidos aventureros, reunidos en comisión de urgencia, diseñan una estrategia para poder cruzar de la manera más veloz posible el vetusto puente colgante.

.

La estrategia ganadora es la siguiente:

1ª ida – Indiana (1 minuto) y Magallanes  (2 minutos) = 2 minutos.

1ª vuelta – Indiana (1 minuto) = 1 minuto.

2ª ida – Cristobal (4 minutos) y Atila (5 minutos) = 5 minutos.

2ª vuelta – Magallanes (2 minutos) = 2 minutos.

3ª ida – Indiana (1 minuto) y Magalles (2 minutos) = 2 minutos.

3ª vuelta – Indiana (1 minuto) = 1 minuto.

4ª ida – Indiana (1 minuto) y Marco Polo (3 minutos) = 3 minutos.

Tiempo total: 16 minutos.

Podemos modelar el problema para el caso de “n” aventureros.

Designamos a los aventureros como P_1, P_2,..., P_n, y sus respectivos tiempos en minutos como T_1 = 1, T_2 = 2,..., T_n = n.

La estrategia consiste en ir pasando iterativamente al otro lado del puente los dos aventureros más lentos.

1ª Iteración

Primero pasarán los dos más rápidos: P_1, P_2 = T_2.

Segundo volverá el más rápido de todos: P_1 = T_1.

Tercero pasarán los dos más lentos: P_n, P_{(n-1)} = T_n.

Cuarto volverá el segundo más rápido: P_2 = T_2.

Tiempo total de la iteración: T_1 + 2T_2 + T_n = n + 5.

2ª Iteración

Primero pasarán los dos más rápidos: P_1, P_2 = T_2.

Segundo volverá el más rápido de todos: P_1 = T_1.

Tercero pasarán los dos más lentos: P_{n-2}, P_{(n-3)} = T_{n-2}.

Cuarto volverá el segundo más rápido: P_2 = T_2.

Tiempo total de la iteración: T_1 + 2T_2 + T_{n-2} = n + 3.

Ultima iteración

(\displaystyle\frac{n-1}{2} si n es impar y \displaystyle\frac{n}{2} si n es par)

———————————————————————————————————–

Para n impar:

Primero pasarán los dos más rápidos: P_1, P_2 = T_2.

Segundo volverá el más rápido de todos: P_1 = T_1.

Tercero pasarán los dos más lentos: P_1, P_3 = T_3.

Tiempo total de la iteración: T_1 + T_2 + T_3 = 6.

———————————————————————————————————–

Sumando todas las iteraciones:

(A) ( Nº de iteraciones – 1 ) * (T_1+2T_2) = (\displaystyle\frac{n-3}{2})*5.

(B) T_1 + T_2 = 3.

(C) T_3 + T_5 + ... + T_n = \displaystyle\sum_{k=1}^{\frac{n-1}{2}} (2k+1)

Tiempo Total de todas las iteraciones: (\displaystyle\frac{n-3}{2})*5 + 3 + \displaystyle\sum_{k=1}^{\frac{n-1}{2}} (2k+1) .

Como \displaystyle\sum_{k=1}^{\frac{n-1}{2}} (2k+1) = (\displaystyle\frac{n+1}{2})^2 - 1 (Ver sumatoria) tenemos:

Tiempo Total = \displaystyle\frac{10n-30+12+n^2+2n+1-4}{4}=\displaystyle\frac{n^2+12n-21}{4}.

———————————————————————————————————–

Para n par:

Primero pasarán los dos más rápidos: P_1, P_2 = T_2.

———————————————————————————————————–

Sumando todas las iteraciones:

(A) ( Nº de iteraciones – 1 ) * (T_1+2T_2) = (\displaystyle\frac{n-2}{2})*5.

(B)  T_2 = 2.

(C) T_4 + T_6 + ... + T_n = \displaystyle\sum_{k=1}^{\frac{n-2}{2}} (2k+2)

Tiempo Total de todas las iteraciones: (\displaystyle\frac{n-2}{2})*5 + 2 + \displaystyle\sum_{k=1}^{\frac{n-2}{2}} (2k+2).

Como \displaystyle\sum_{k=1}^{\frac{n-2}{2}} (2k+2) = (\displaystyle\frac{n^2+2n-8}{4}) (Ver sumatoria) tenemos:

Tiempo Total = \displaystyle\frac{10n-20+8+n^2+2n-8}{4}=\displaystyle\frac{n^2+12n-20}{4}.

Anuncios
Esta entrada fue publicada en Lógica y etiquetada , , , , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s