There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.

Woman 1: 1 minute to cross

Woman 2: 2 minutes to cross

Woman 3: 5 minutes to cross

Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

## 3 comments:

Hint :

You have 17 minutes to get all of them across to the other side.

Solution :

The following sequence is the optimized sequence :

STEP 1 :

Pair crossing : W1, W2

Returning : W1

Time spent : 2 + 1 = 3 minutes

Women still to cros : W1, W3, W4

STEP 2 :

Pair crossing : W3, W4 (

greedy)Returning : W2

Time spent : 10 + 2 = 12 minutes

Women still to cros : W1, W2

STEP 3 :

Pair crossing : W1, W2

Returning : none

Time spent : 2 = 2 minutes

Women still to cross : none

Total time : 2 + 12 + 3 = 17 minutes

Extra bonus :

This problem has been quoted in multiple variants in multiple process scheduling algorithm discussions.

Once such paper : http://www.cs.umass.edu/~mcgregor/papers/04-fun.pdf

Post a Comment