Man 1: 1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross

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

 

General Comment: For this riddle, the major lesson is to learn how to carefully enumerate all possibilities. We need to find a good way to search through the space of possible moves, and find the sequence of moves that has the shortest time.

 

First Thought: How many possible first moves are there? There are four ways to move just one person over (send just 1, just 2, just 5 or just 10), and there are six ways to send two people over (send 1 and 2, send 1 and 5, send 1 and 10, send 2 and 5, or send 5 and 10).  Can we eliminate any of these possibilities?

 

Second Thought: It makes no sense to just send one person over, as they’d have to return immediately. Thus two people go over in the first move. So our first move is either

(1,2) go over
(1,5) go over
(1,10) go over
(2,5) go over
(2,10) go over
(5,10) go over

We have to figure out which of these moves we should make, and then who goes back. If (5, 10) go over that costs 10 minutes, and then even if 5 returns that’s still another 5 minutes, for 15 minutes total. A little work shows there is no way to get 1, 2 and 5 over in 2 minutes (we have to get 5 back!). Similarly we see that we can’t send 2 and 10 over together: that costs 10 minutes, and sending 2 back brings our total to 12 minutes. We would then have to get 1, 2 and 5 over in just 5 minutes, and we can’t do that.

We thus must send either (1,2) or (2,5). It seems reasonable to try to send 5 and 10 over together, as they are the slowest. Thus, we might want to try sending (1,2) over as our first move.

 

Third Thought: For problems like these, it helps to develop a good notation to keep track of who is where and when, and how much time has elapsed. This is a great skill to get — whenever you have a problem, try to distill the key parts of it and come up with a notation that emphasizes what matters. For this problem, we can have four columns. The first will be who is on the left, the next who is moving and in what direction, then who is on the right,  and finally how much total time has elapsed.

Thus if we initially send (5,10) over, then 5 back, then (1,5) over, then 1 back, then (1,2) over we would write:

LEFT          MOVING     RIGHT     TIME

1,2,5,10                                              0

1,2             5,10 –>                            0

1.2                                    5, 10         10

1,2             <– 5             10               10

1,2,5                                10              15

2                1,5 –>           10              15

2                                        1,5,10      20

2                <– 1               5,10         20

1,2                                    5,10          21

1,2 –>            5,10         21

1,2,5,10  23

Obviously this is NOT the solution, but a nice way to write odwn the sequence of moves.

 

Fourth Thought: We send (1,2) over and we can try sending back either 1 or 2. It turns out both choices work. If we send 1 back, we have (1,5,10) on the left, 2 on the right, and 3 minutes have passed.

 

Final Thought: The analysis above uses logical deductions to prune the possibilities. There is a way to attack this problem using graphs. What I like about this approach is it introduces us to another powerful technique, graph theory. A graph is a collection of vertices (or nodes) and edges connecting them. For this problem, we write the nodes as (x | y), where x represents the people on the left and y the people on the right. If no one is on a side we represent it by –. Thus our possible nodes are: (1 2 5 10 | — ), (1 2 5 | 10), (1 2 10 | 5), (1 5 10 | 2), (2 5 10 | 1), (1 2 | 5 10), … and so on until we reach (– | 1 2 5 10). We then draw an edge from any vertex to any other if we can go from one to another by a legal move. Thus we can go from (1 2 5 | 10) to (1 | 2 5 10) by sending 2 and 5 over, so we can draw an edge and label it with a 5 (to denote the time elapsed). We can’t move from (1 2 5 | 10) to (1 10 | 2 5) in one move, so there will be no edge connecting these. “All” we need to do is look at all paths from (1 2 5 10 | — ) to ( — | 1 2 5 10)  and see which takes 17 minutes.

Unfortunately, as we try to construct the graph we realize we need more information. We need to keep track of where the flashlight is, as we can’t send people without a flashlight. Thus (1 2 5 * | 10) means 1 2 5 and the flashlight are on the left and 10 is on the right, while (1 2 5 | 10 *) has the same distribution of people but the flashlight is on the right.

If we use this approach, it will be a long process, but we will get the solution. It’s important to know a method that will work, and then try to find an efficient one!

 

Additional Comments: The following comment is from my student Anand Hemmady: If we look at the problem, it is logical that two things are necessary for us to minimize the time spent:

1) The individuals who take 5 and 10 minutes must only cross once.

2) The individuals who take 5 and 10 minutes must cross at the same time.

The first of these criteria is easy to implement, but the second one is a little trickier. At first, I wasn’t sure how to go about implementing it, as it isn’t something that I thought of immediately. We must first have the individuals who take 1 and 2 minutes cross. Then, have one of them go back (it doesn’t matter which one, as the other one will also have to go back later). Next, have the individuals who take 5 and 10 minutes cross together. This way, we satisfy both of our criteria above; they only cross once and they cross together. Next, have the individual who remained on the other side come back. Last, have the individuals who take 1 and 2 minutes cross back together.