Math Goodies is a free math help portal for students, teachers, and parents.
|
Interactive Math Goodies Software

testing left nav
Math Forums @ Math Goodies
Home | Profile | Register | Active Topics | Members | Search | FAQ
 All Forums  Homework Help Forums  Miscellaneous Math Topics  Bridge Crossing New Topic  Reply to Topic  Printer Friendly
Author  Topic

TchrWill

USA
78 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

295 Posts

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

Ultraglide

295 Posts

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

TchrWill

USA
78 Posts

 Posted - 08/16/2013 :  11:52:37 quote:Originally posted by UltraglideThis is even better:1 and 10 cross - 10 minutes1 returns - 1 minute1 and 5 cross - 5 minutes1 returns - 1 minute1 and 2 cross - 2 minutestotal - 19 minutesGetting close.

the_hill1962

USA
1461 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

USA
78 Posts

 Posted - 08/20/2013 :  16:40:52 quote:Originally posted by the_hill1962This 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

USA
1461 Posts

 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 minutesThey toss the flashlight back over (it is still turned on so it can be seen).The 2 and 1 person cross === 2 minutesTotal 12 minutes.quote:Originally posted by TchrWillquote:Originally posted by the_hill1962This 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

USA
78 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: 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 Sidea-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 Edited by - TchrWill on 08/28/2013 20:51:07
Topic
 New Topic  Reply to Topic  Printer Friendly Jump To: Select Forum New Visitor Forum       Testing Forum Homework Help Forums       Basic Math and Pre-Algebra       Algebra       Geometry and Trigonometry       Pre-Calculus and Calculus       Probability and Statistics       Standardized Test Preparation Help       Miscellaneous Math Topics Educator Forum       Teacher Talk Parent Forum       Parent's Place  -------------------- Home Active Topics Frequently Asked Questions Member Information Search Page
 Math Forums @ Math Goodies © 2000-2004 Snitz Communications