Saturday, January 10, 2009

Problem solving: bridges

Four guys are on the left side of a bridge and they need to go to the right side. It is night and the guys have just one electric torch light. Each guy has a different walking time. Namely, 10 second, 5 second, 2 second, and 1 second. At most 2 guys can be on the bridge at the same time, and when they walk in pair they have the speed of the slowest guy.

What it the minimum time to have the four guys on the right side of the bridge?


  1. Hint: when a pair of guys go on the right side of the bridge, one of them must return back to bring the light to the other guys. You need to minimize this overhead. (minimum cost is 17)

  2. 1) 1 and 2 will go to other end and 1 will come back
    total time - 2+1 = 3;
    2)5 and 10 will go and 2 will come back
    total time - 10 + 2 = 12
    3) 1 and 2 will go
    total time : 2

    Cumulative total time : 3 + 12 +2 = 17