A group of four students wish to cross a bridge without side rails in the middle of the jungle very late at night. They have one lantern to share. No one may take a step without holding the lantern (it's dark at night with no moon). No more than two people may be on the bridge at one time, not even for a moment. What is the shortest time it would take for all of them to get across? Use the following information to solve the problem:
The first student, Lauren, can cross the bridge alone in 5 minutes. (She’s a track star.)
The second student, Emma, can cross the bridge alone in 10 minutes.
The third student, Rochelle, can cross the bridge alone in 20 minutes.
The fourth student, Molly, can cross the bridge alone in 25 minutes. (She has a sore ankle).
Now, when two students walk together, they must move at the rate of the slowest person!
Consider a simpler, more general case..
Assuming we are seeking the least time.
* Let the four people be labeled a, b, c, and d in ascending order of their walking times.
* After reviewing the following hints, you will easily be able to conclude that the minimum crossing time can always be accomplished in T = a + 3b + d minutes which in this case results in T = 1 + 3(2) + 10 = 17 minutes but we will ignore this for the time being.
* Clearly, one person has to return across the bridge with the flashlight to accompany the next person across.
HINTS:
1--Since only one person can be permanently taken across at a time, we know that there will be 5 trips made in all; 3 trips bringing a person over and 2 trips where 1 person returns to get another person.
2--By definition, one of the trips across must take 10 minutes dictated by "d's" walking time.
3--Logically the two people taking the highest times, "c and "d", will cross together taking 10 minutes to cross over.
4--We can safely conclude that neither the 5 minute or 10 minute walker will return for "a" or "b" as they as "a" and "b" will consume less time crossing over.
5--This leaves "a" and "b", the two people taking the two shortest times, to arrange their crossings in such a way as to consume the minimum amount of time.
6--Four trips consuming 1 or 2 minutes can be achieved in one of four ways; 2+2+2+2, 1+2+2+2, 1+1+2+2, or 1+1+1+2, not necessarily in these orders however. Four trips of 1 minute is impossible as at least one trip must be made at "b's" time.
7--Person "a's" crossing time can only enter into the result if "a" travels alone since when traveling with "b", their crossing time would have to be 2 minutes.
8--Therefore, we should try to have "a" make one return trip by himself meaning that he must go across with "b" once and return by himself once.
9--We now assume that "a" and "b" make at least one trip across together taking 2 minutes, "a" makes one trip returning to the starting side taking 1 minute, and "c" and "d" make one trip across taking 10 minutes, consuming in all 2 + 1 + 10 = 13 minutes in three trips.
10--Clearly, we can eliminate the 2+2+2+2 case.
11--What are our options now? SInce "c" and "d" make one trip across without returning, "a" and "b" must shuttle back and forth in some manner so as to consume 5 to 7 minutes.
12--Either "a" and "b" or "c" and "d" can cross first.
13--Obviously, if "c" and "d" go across first, only "c" could sensibly return taking 5 minutes thereby consuming 15 minutes on the first two trips.
14--Since our total time is known to be 15 to 17 minutes, clearly "c" and "d" cannot cross over first.
15--Let "a" and "b" make the 1st trip taking 2 minutes.
16--Either "a" or "b" can now return. Let "b" return taking 1 minute.
17--We now have a, c, and d on one side and "b" on the other side.
18--This is logically where we let "c" and "d" cross over taking 10 minutes.
19--We now have "a" on one side with b, c, and d crossed over.
20--Clearly, "b" returns taking 2 minutes.
21--Finally, "a" and "b" cross over taking 2 minutes for a grand total of 17 minutes.
..Start Crossing Other Side
a-b-c-d - -
..c-d -----a-b------> -
..c-d - a-b
<-----a--------- b
.a-c-d - b
....a ------c-d------> b
....a - b-c-d
<------b------- c-d
...a-b - c-d
.............-----a-b------> c-d
- - a-b-c-d
Now try your problem.
