Thursday, 13 August 2015

graph theory - Shortest time for passing the bridge t(t1,t2,t3,dots;textMax,textMin)

A1 can pass a bridge in 1 minute, A2 can pass the bridge in 2 minutes, A3 can pass the bridge in 5 minutes, and A4 can pass the bridge in 10 minutes. This bridge can hold at most two people at a time. Also, a torch must be used while passing the bridge since it is dark. People who are moving on the bridge must walk adjacently. What is the shortest period of time so that all A1,A2,A3,A4 move to the other side of the bridge?






The answer is 17 minutes, the strategy is as follows:



A1 and A2 go together to the other side (2 minutes completed)



A1 goes back to A3 and A4 because they need the torch (3 minutes completed)




A3 and A4 go together to the other side (13 minutes completed)



A2 goes back to A1 because he needs the torch (15 minutes completed)



A1 and A2 go to the other side (17 minutes completed)






Now the problem can be rewritten as t(time by A1, time by A2, ; maximum number of people going, minimum number of people coming back)




So in this case, t(1,2,5,10;2,1)=17






Say we have this problem:



A1 can pass a bridge in 1 minute, A2 can pass the bridge in 2 minutes, A3 can pass the bridge in 5 minutes, A4 can pass the bridge in 10 minutes, and A5 can also pass the bridge in 10 minutes . This bridge can hold at most four people and at least two people at a time. Also, a torch must be used while passing the bridge since it is dark. People who are moving on the bridge must walk adjacently. What is the shortest period of time so that all A1,A2,A3,A4,A5 move to the other side of the bridge?



In other words, how to find t(1,2,5,10,10;4,2)?







In general, how to find t(t1,t2,t3,;Max,Min)



Must we use trial and error way? What if we have to find



t(1,2,2,2,3,4,7,9,9,15;7,4)?



I already saw this. But it is not exactly my problem.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...