Am primit soluţii corecte de la Zoltan Szabo, Lucian Niţă, Angela Sandu, Aurel Ionescu, Marian Baloo, Irina Spânu, Camelia Muşetescu, Dan Florescu, Emil Claudiu Man, Viorel Manta, Cristian Bălănoiu.

Toţi au găsit o traversare în 29 secunde.

Dau soluţia lui Zoltan Szabo, care cuprinde şi o generalizare:

Pasul 1.    3 secunde 

                      traverseaza 1+3               (1,3)

Pasul 2.   1 secunda

                     revine 1                            (3)

Pasul 3.   12 secunde

                      traverseaza 8+12            (3,8,12)

Pasul 4.   3 secunde

                     revine 3                           (8,12)

Pasul 5.   6 secunde

                      traverseaza 1+6            (1,6,8,12)

Pasul 6.   1 secunda

                     revine 1                           (6,8,12)

Pasul 7.   3 secunde

                      traverseaza 1+3            (1,3,6,8,12)

Timpul necesar parcugerii podului: 3+1+12+3+6+1+3=29 de secunde

 Generalizare:

N persoane vor să traverseze un pod. Timpii de traversare pentru fiecare persoană în ordine crescătoare sunt următoarele t≤ t≤ t≤ t≤... ≤ tN-1 ≤ tN. Podul fiind şubred, nu pot trece mai mult de două persoane. În plus, este noapte, şi au o singură lanternă la dispoziţie... Să se calculeze timpul minim necesar traversării podului.

Rezolvare:

Dacă N=1 persoana traverseaza direct în timp t1.

Dacă N=2 persoanele traverseaza direct în timp t2.

Dacă N=3, timpul minim este t1+t2+tşi se obţine astfel: prima dată vor trece 1 şi 3 îu timpul t3, apoi 1 se întoarce în timp t1 iar în final 1 şi 2 vor trece în timp t2.

Dacă N=4, în funcţie de valorile t, 1≤i≤4 alegem una din două variante de traversare:

      varianta a.

1. trece 1 şi 2 în timp t2,

2. revine 1 în timp t1,

       3. trece 1 şi 3 în timp t3,

       4. revine 1 în timp t1,

       5. trece 1 şi 4 în timp t4,

Timpul total de traversare este 2t1+t2+t3+t4

      varianta b.

1. trece 1 şi 2 în timp t2,

2. revine 1 în timp t1,

       3. trece 3 şi 4 în timp t4,

       4. revine 2 în timp t2,

       5. trece 1 şi 2 în timp t2,

Timpul total de traversare este t1+3t2+t4

Comparăm duratele de timp pentru cele două variante, studiind în ce condiţii este mai avantajoasă varianta a doua:

t1+3t2+t< 2t1+t2+t3+t4   sau după reducerea termenilor 2t< t1+t3

Deci dacă 2t< t1+t3, vom alege varianta 2, altfel alegem varianta 1 pentru traversare.

Observaţie: în caz de egalitate 2t= t1+t3, ambele variante de traversare vor da acelaşi rezultat de timp.

Dacă N=5, în funcţie de valorile t, 1≤i≤5.

Vom proceda ca la n=4 pentru persoanele t1, t2, t4, t5. Adică dacă 2t< t1+t4  se alege varianta cu timpul de traversare t1+3t2+t5

1. trece 1 şi 2 în timp t2,

2. revine 1 în timp t1,

       3. trece 4 şi 5 în timp t5,

       4. revine 2 în timp t2,

       5. trece 1 şi 2 în timp t2,

În caz contrar (2t> t1+t4, cazul de egalitate admite ambele variante de rezolvare), timpul de traversare va fi 2t1+t2+t4+t5

1. trece 1 şi 2 în timp t2,

2. revine 1 în timp t1,

       3. trece 1 şi 4 în timp t4,

       4. revine 1 în timp t1,

       5. trece 1 şi 5 în timp t5,

În continuare

6. revine 1 în timp t1

7. trece 1 şi 3 în timp t3.

Timpul necesar pentru paşii 6 şi 7 este t1+t3. Totalul timpului parcurs va fi min(2t1+3t2+t3+t5,3t1+t2+t3+t4+t5)

 În cazul general, când N>5, avem în vedere următoarele proprietăţi ştiind că timpii de execuţie sunt în ordine crescătoare t≤ t≤ t≤ t≤... ≤ tN-1 ≤ tN

Algoritmul se prezintă în felul următor:

Fie şirul timpilor de traversare t1, t2, t3, t4,... tN-1, tN

În acest şir c