Author 
Topic 

TchrWill
Advanced Member
USA
80 Posts 
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.

Edited by  TchrWill on 08/14/2013 13:02:17 


Ultraglide
Advanced Member
Canada
299 Posts 
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 


Ultraglide
Advanced Member
Canada
299 Posts 
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 


TchrWill
Advanced Member
USA
80 Posts 
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. 


the_hill1962
Advanced Member
USA
1470 Posts 
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
Advanced Member
USA
80 Posts 
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
Advanced Member
USA
1470 Posts 
Posted  08/26/2013 : 13:30:23

Okay, I will take out the "if not caught" (no "whatifs"): 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."

Edited by  the_hill1962 on 08/26/2013 13:32:19 


TchrWill
Advanced Member
USA
80 Posts 
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: 1Since 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. 2By definition, one of the trips across must take 10 minutes dictated by "d's" walking time.. 3Logically the two people taking the highest times, "c and "d", will cross together taking 10 minutes to cross over. 4We 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. 5This 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. 6Four 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. 7Person "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. 8Therefore, 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. 9We 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. 10Clearly, we can eliminate the 2+2+2+2 case. 11What 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. 12Either "a" and "b" or "c" and "d" can cross first. 13Obviously, if "c" and "d" go across first, only "c" could sensibly return taking 5 minutes thereby consuming 15 minutes on the first two trips. 14Since our total time is known to be 15 to 17 minutes, clearly "c" and "d" cannot cross over first. 15Let "a" and "b" make the 1st trip taking 2 minutes. 16Either "a" or "b" can now return. Let "b" return taking 1 minute. 17We now have a, c, and d on one side and "b" on the other side. 18This is logically where we let "c" and "d" cross over taking 10 minutes. 19We now have "a" on one side with b, c, and d crossed over. 20Clearly, "b" returns taking 2 minutes. 21Finally, "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 abcd   ..cd ab>  ..cd  ab <a b .acd  b ....a cd> b ....a  bcd <b cd ...ab  cd ... ab> cd  abcd

Edited by  TchrWill on 08/28/2013 20:51:07 



Topic 


