SOLUCIÓN AO PROBLEMA DE COMO CRUZAR UN RÍO POR UNHA PONTE

Problema-solución / Imaxe: marketingdirecto.com/

Lembrades a pregunta do problema? Como realizarán os cruces, dun a outro lado do río, para tardar o mínimo tempo posible en cruzalo todos? Calcular tamén o tempo mínimo para o caso de n persoas.

Resolvéstelo? Imos ver a solución:

Chamaremos “beira A” á beira no que inicialmente se atopan e “beira  B” á beira contraria, que será o do destino. Tamén denotaremos a cada persoa polo tempo que tarda en cruzar.

A estratexia que leva ao tempo mínimo consiste no seguinte:

- Se as dúas persoas 1 e 2 atópanse na “beira A”, cruzarán ambas.
- Se algunha das persoas 1 e 2 atópanse na “beira  B”, cruzará a persoa 1 para devolver a lanterna ás da “beira A”.
- Se só una das persoas 1 ou 2 atópanse na “beira A”, cruzarán as dúas persoas que máis tempo tardan.

Con esta estratexia, podemos establecer a seguinte fórmula recursiva:

T(n) =  T(n – 2) +  n + 5.

Para iso, con  n persoas, pasan primeiro as persoas 1 e 2 (dous minutos), volve a persoa 1 (un minuto), pasan as persoas  n e  n – 1 ( n minutos) e volve a persoa 2 (dous minutos). Neste momento, o problema redúcese ao de  n – 2 persoas.

Aplicando sucesivamente esta fórmula, obtense a fórmula explícita

T(2 n + 1) =  n2 + 7 n – 2;  T(2 n) =  n2 + 6 n – 5.

No caso proposto (n = 5), é  T = 16 minutos.

FONTE: zientzia-astea.org/es