I thought this was great. It’s a little brain teaser, an optimization problem; and it’s of the type that you KNOW as soon as it’s asked that the “real” answer is different than the intuitive answer. The problem goes like this:

It’s nighttime in the jungle. Four men (A, B, C, and D) approach a bridge crossing a deep ravine. The bridge is old and decrepit, and only two men can cross the bridge at the same time. Further, the men are in different physical condition, so it takes A 1 minute, B 2 minutes, C 5 minutes, and D 10 minutes to cross. Because it’s nighttime, and the bridge is full of holes and loose boards, and the men carry only one light among them, each twosome must carry the single light and cross as a team, thus the joint trip takes as long as the slowest man of the twosome.

The light can not be thrown across the ravine; it must be carried back across by one man.

How do you minimize the trip time to get all four men across the bridge?

**SPOILERS AHEAD**

Instinct tells you that the fast guy – A – has to do the return trips with the light, to minimize the “light return” portion of the trips. So you may arrive at the following pretty quickly:

Trip | Time | Accrued |

A and B cross | 2 minutes | 2 minutes |

A returns with light | 1 minute | 3 minutes |

A and C cross | 5 minutes | 8 minutes |

A returns with light | 1 minute | 9 minutes |

A and D cross | 10 minutes | 19 minutes |

However, you know from the type of problem that there’s a better way to get across. You might surmise that there should be a way to “hide” the travel time of C (the second-slowest) within the travel time of D (the slowest; if C and D go across together, then you “save” maybe 3 or 4 minutes, because C wouldn’t have to slow A or B down when C travels with either of those two.

So how do you get C and D across the bridge together? Well, if they go first, then you have to take 10 minutes across, and another 5 minutes while C comes back with the light. Not so good, since A (if he were already on the other side of the bridge) would only take 1 minute for the return trip, thus this eats up your savings.

So how do you get A across the bridge such that he can return from the trip with C and D? Pair him with B? Hmm…

Trip | Time | Accrued |

A and B cross | 2 minutes | 2 minutes |

B returns with light | 2 minutes | 4 minutes |

C and D cross | 10 minutes | 14 minutes |

A returns with light | 1 minute | 15 minutes |

A and B cross | 2 minutes | 17 minutes |

Voila. This is the type of problem where it really helps to write it out (like on a blog!) and work through the assumptions and requirements step-by-step. The key line in the whole post is:

**So how do you get A across the bridge such that he can return from the trip with C and D?**

Once you’ve reached that stage in the reasoning, you can quickly get to the correct solution of 17 minutes.

I found this problem in the wonderful book How to Solve It: Modern Heurstics (2nd Ed.), by Michalewicz and Fogel.

## 0 Responses to “The Bridge Problem”