Thursday, January 12, 2012

minimize the time taken by all 4 to cross the bridge.

There is a bridge and to travel on it there should be a torch light available.
Only two persons can cross the bride at a time. There are 4 persons on the other side of the bridge. They require 1,2,5,10 minutes respectively to cross the bridge. How much time should it take for all 4 to go to the other side of the bridge.

Remember there is only one torch light. So if two persons cross the bridge with torch light, one has to come back with torch light for others to use torch light. If person with 1 min and 10 minutes cross the bridge together, they take 10 minutes together to cross the bridge(maximum of the time taken by two people).

Your criteria is to minimize the time taken by all 4 to cross the bridge.


1 comment:

Soham Chakraborty said...

The minimum time taken will be 17 minutes.

Solution:
Let the persons taking 1,2,5,10 be labelled as P1, P2, P3, P4 respectively.

1. Send P1 and P2 together to other end. ( 2 minutes)

2. Send P1 back (1 minute)

3. Send P3 and P4 to the other end. (10 minutes)

4. Send P2 back ( 2 minutes)

5. Send P1 and P2 to the other side. ( 2 minutes.

Done. ( 2 + 1 + 10 + 2 + 2 = 17 minutes)