testing header
Math Goodies is a free math help portal for students, teachers, and parents.
Free Math
Newsletter
 
 
Interactive Math Goodies Software

Buy Math Goodies Software
testing left nav
Math Forums @ Math Goodies
Math Forums @ Math Goodies
Home | Profile | Register | Active Topics | Members | Search | FAQ
 All Forums
 Homework Help Forums
 Miscellaneous Math Topics
 Bridge Crossing

Note: You must be registered in order to post a reply.
To register, click here. Registration is FREE!

Screensize:
UserName:
Password:
Format Mode:
Format: BoldItalicizedUnderlineStrikethrough Align LeftCenteredAlign Right Horizontal Rule Insert HyperlinkInsert EmailInsert Image Insert CodeInsert QuoteInsert List Insert Special Characters Insert Smilie
   
Message:
* HTML is OFF
* Forum Code is ON

Math Symbols
Squared [squared] Cubed [cubed] Square Root [sqrt] Cube Root [cbrt] Pi [pi]
Alpha [alpha] Beta [beta] Gamma [gamma] Theta [theta] Angle [angle]
Degrees [degrees] Times [times] Divide [divide] Less Than or Equal To [less-than] Greater Than or Equal To [greater-than]
Plus Minus [plus-minus] Integral [integral] Sum [sum] Sub 1 [sub-1] Sub 2 [sub-2]
Element Of [element-of] Union [union] Intersect [intersect] Subset [subset] Empty Set [empty-set]

  Check here to subscribe to this topic.
 
   

T O P I C    R E V I E W
TchrWill 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

Math Forums @ Math Goodies © 2000-2004 Snitz Communications Go To Top Of Page
This page was generated in 0.19 seconds. Snitz Forums 2000
testing footer
About Us | Contact Us | Advertise with Us | Facebook | Blog | Recommend This Page




Copyright © 1998-2014 Mrs. Glosser's Math Goodies. All Rights Reserved.

A Hotchalk/Glam Partner Site - Last Modified 30 Oct 2014