Posted - 08/14/2013 : 10:43:38 Four persons want to cross a bridge during a dark moonless night. The bridge is strong enough to hold only two persons at at time. A flashlight must be used when crossing the bridge, and there is only one flashlingt available. So at most two persons at a time can cross the bridge using one flash light. One person can cross the bridge with a flash light in 1 minute. The other three persons can each do the same in 2, 5 and 10 minutes, respectively. The task is for them to all cross the bridge in the least time.

7 L A T E S T R E P L I E S (Newest First)

TchrWill

Posted - 08/28/2013 : 16:47:45 No short bridges.

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 for the next pair to cross. . 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.

Simpler yet: 1—Clearly, one trip must be made by the pair having 5 and 10 minute crossing times leaving the remainder of the trips to be accomplished by the 1 and 2 minute crossing people. 2—There being no need to make any further trips with 5, and or 10, we need only find a way to employ 1 and 2 safely to the other side in the least number of transits.

..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

the_hill1962

Posted - 08/26/2013 : 13:30:23 Okay, I will take out the "if not caught" (no "what-ifs"): Leaving the flashlight on, all of them can cross the bridge in 12 minutes---- The 10 and 5 person cross === 10 minutes They toss the flashlight back over (it is still turned on so it can be seen). The 2 and 1 person cross === 2 minutes Total 12 minutes.

quote:Originally posted by TchrWill

quote:Originally posted by the_hill1962

This is just a shot in the dark (pun intended): Instead of walking the flashlight back to the other side, couldn't it just be thrown back over? True, it could be said that the flashlight could not be caught or it would be lost since it is dark. However, what about just leaving the flashlight on when throwing it back over. True, there is a risk that it might break if not caught and then it couldn't be found. The problem did not specify if it was a rugged flashlight.

A flashlight must be used when crossing the bridge, and there is only one flashlight available. No "whatiffs."

TchrWill

Posted - 08/20/2013 : 16:40:52

quote:Originally posted by the_hill1962

This is just a shot in the dark (pun intended): Instead of walking the flashlight back to the other side, couldn't it just be thrown back over? True, it could be said that the flashlight could not be caught or it would be lost since it is dark. However, what about just leaving the flashlight on when throwing it back over. True, there is a risk that it might break if not caught and then it couldn't be found. The problem did not specify if it was a rugged flashlight.

A flashlight must be used when crossing the bridge, and there is only one flashlight available. No "whatiffs."

the_hill1962

Posted - 08/20/2013 : 07:41:11 This is just a shot in the dark (pun intended): Instead of walking the flashlight back to the other side, couldn't it just be thrown back over? True, it could be said that the flashlight could not be caught or it would be lost since it is dark. However, what about just leaving the flashlight on when throwing it back over. True, there is a risk that it might break if not caught and then it couldn't be found. The problem did not specify if it was a rugged flashlight.

TchrWill

Posted - 08/16/2013 : 11:52:37

quote:Originally posted by Ultraglide

This is even better: 1 and 10 cross - 10 minutes 1 returns - 1 minute 1 and 5 cross - 5 minutes 1 returns - 1 minute 1 and 2 cross - 2 minutes total - 19 minutes

Getting close.

Ultraglide

Posted - 08/15/2013 : 12:12:57 This is even better: 1 and 10 cross - 10 minutes 1 returns - 1 minute 1 and 5 cross - 5 minutes 1 returns - 1 minute 1 and 2 cross - 2 minutes total - 19 minutes

Ultraglide

Posted - 08/14/2013 : 17:16:01 Here's my solution: 10 and 5 cross together - 10 minutes 5 returns - 5 minutes 1 and 2 cross together - 2 minutes 1 returns - 1 minute 1 and 5 cross together - 5 minutes total - 23 minutes