Bridge crossing problem

There are four men who would all like to cross a rickety old bridge.
(Perhaps it is more accurate to say that they'd like to get to the
other side.) The old bridge will only support 2 men at a time, and it is
night time, so every crossing must use the one flashlight that they all
share. The four men each have different walking speeds; the fastest each
of them can cross is 1 minute, 2 minutes, 5, minutes, and 10 minutes. If
they pair up, since they must share the flashlight, they can only cross
in the time that it would take the slower of the two. Given that the
shortest time to get them all across is 17 minutes total, how should
they all cross?




1, 2 go together, drops 2 and comes back, taking 3 minutes
(1,2)-------> 2
<------

5,10 go together, taking 10 minutes
(5,10)------> 2, 5, 10

Now, 2 comes back with the light
and takes 1 to the other side, taking 4 minutes

Note, its efficient to club 5,10.

No comments: