The Bridge Problem

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.

Advertisements

0 Responses to “The Bridge Problem”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s





%d bloggers like this: