0
$\begingroup$

$A_1$ can pass a bridge in $1$ minute, $A_2$ can pass the bridge in $2$ minutes, $A_3$ can pass the bridge in $5$ minutes, and $A_4$ 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 $A_1,A_2,A_3,A_4$ move to the other side of the bridge?


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

$A_1$ and $A_2$ go together to the other side ($2$ minutes completed)

$A_1$ goes back to $A_3$ and $A_4$ because they need the torch ($3$ minutes completed)

$A_3$ and $A_4$ go together to the other side ($13$ minutes completed)

$A_2$ goes back to $A_1$ because he needs the torch ($15$ minutes completed)

$A_1$ and $A_2$ go to the other side ($17$ minutes completed)


Now the problem can be rewritten as $t($time by $A_1$, time by $A_2$, $\dots$; 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:

$A_1$ can pass a bridge in $1$ minute, $A_2$ can pass the bridge in $2$ minutes, $A_3$ can pass the bridge in $5$ minutes, $A_4$ can pass the bridge in $10$ minutes, and $A_5$ 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 $A_1,A_2,A_3,A_4,A_5$ 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(t_1,t_2,t_3,\dots;\text{Max},\text{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.

$\endgroup$
0
$\begingroup$

You can formulate this as a shortest path problem, with a node for each placement of people and the torch on one side or the other of the bridge and an edge between nodes for each possible transition, with cost equal to the time of traversal. The source node has all people and the torch on one side, and the sink node has all people and the torch on the other side.

I confirm that $t(1,2,5,10;2,1) = 17$.

Also, $t(1,2,5,10,10;4,2) = 17$, which you can achieve as follows:

{A1,A2,A3}    cost = max(1,2,5)     = 5
{A1,A2}       cost = max(1,2)       = 2
{A1,A2,A4,A5} cost = max(1,2,10,10) = 10

And $t(1,2,2,2,3,4,7,9,9,15;7,4) = 24$, as follows:

{A1,A2,A3,A4,A5,A6,A7}  cost = 7
{A1,A2,A3,A4}           cost = 2
{A1,A2,A3,A4,A8,A9,A10} cost = 15
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.