I need some help getting this problem set up.I know one has to travel back and forth so that limits to one at a time to cross at the slowest pace.Just getting confused.
Four people are trying to cross a bridge in the dark. The bridge is old, and can only hold two of the people at any one time. They have only one flashlight, which must be carried by someone each time the bridge is crossed. The flashlight is weak, so it is not possible to stand in the middle of the bridge and guide someone across. Each person must walk across the bridge and either carry the light or walk with someone who is carrying the light. The fastest person can cross the bridge in one minute, the second fastest needs two minutes, the third fastest crosses in five minutes, and the slowest takes ten minutes. What is the shortest amount of time that all four can cross the bridge.
* 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
