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
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Homework Help Forums
 Miscellaneous Math Topics
 Bridge Crossing
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

TchrWill
Advanced Member

USA
80 Posts

Posted - 08/14/2013 :  10:43:38  Show Profile  Reply with Quote
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
Go to Top of Page

Ultraglide
Advanced Member

Canada
299 Posts

Posted - 08/14/2013 :  17:16:01  Show Profile  Reply with Quote
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
Go to Top of Page

Ultraglide
Advanced Member

Canada
299 Posts

Posted - 08/15/2013 :  12:12:57  Show Profile  Reply with Quote
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
Go to Top of Page

TchrWill
Advanced Member

USA
80 Posts

Posted - 08/16/2013 :  11:52:37  Show Profile  Reply with Quote
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.
Go to Top of Page

the_hill1962
Advanced Member

USA
1468 Posts

Posted - 08/20/2013 :  07:41:11  Show Profile  Reply with Quote
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.
Go to Top of Page

TchrWill
Advanced Member

USA
80 Posts

Posted - 08/20/2013 :  16:40:52  Show Profile  Reply with Quote
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."

Go to Top of Page

the_hill1962
Advanced Member

USA
1468 Posts

Posted - 08/26/2013 :  13:30:23  Show Profile  Reply with Quote
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."




Edited by - the_hill1962 on 08/26/2013 13:32:19
Go to Top of Page

TchrWill
Advanced Member

USA
80 Posts

Posted - 08/28/2013 :  16:47:45  Show Profile  Reply with Quote
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




Edited by - TchrWill on 08/28/2013 20:51:07
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
Math Forums @ Math Goodies © 2000-2004 Snitz Communications Go To Top Of Page
This page was generated in 0.08 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 21 May 2014