The Bridge and Torch, math that surprises you lesson

Four people must cross a narrow bridge at night with a single torch. They take 1, 2, 5 and 10 minutes to cross, at most two can be on the bridge at once, and a pair walks at the pace of the slower person. Letting the fastest walker escort everyone across takes 19 minutes. Can all four be across in 17? This page finds a 17-minute schedule, shows why the obvious plans fall short, and proves that no schedule is faster.

Key terms

Bridge and torch problem

Definition In the bridge and torch problem, four walkers who take $1$ , $2$ , $5$ and $10$ minutes to cross a bridge start together on one side at night with one torch. Call them walker 1, walker 2, walker 5 and walker 10, after their times. At most two people may be on the bridge at once, and nobody may cross without the torch, so every crossing carries the torch and it gets back to the starting side only when someone carries it back. A walker crossing alone takes their own time, and two walkers crossing together take the time of the slower one. Since there is one torch, the crossings happen one after another, and the total time is the sum of the times of all the crossings. The goal is to get all four to the far side in the least total time. The least total is $17$ minutes, reached when walkers 1 and 2 cross, walker 1 returns, walkers 5 and 10 cross, walker 2 returns, and walkers 1 and 2 cross again. No schedule takes less than $17$ minutes.

In plain words Walker 5 can go along with walker 10 at no extra cost, provided that a fast walker is already waiting on the far side to bring the torch back. As in The River-Crossing Shuttle, the trick is to place someone across in advance for the return trip.

Example The table follows the 17-minute schedule.

Crossing	Who crosses	Minutes	Running total
1	walkers 1 and 2, forward	$2$	$2$
2	walker 1, back	$1$	$3$
3	walkers 5 and 10, forward	$10$	$13$
4	walker 2, back	$2$	$15$
5	walkers 1 and 2, forward	$2$	$17$

Every crossing carries the torch from the side where it is. After crossing 2, walker 2 waits on the far side, and that is what lets walker 2 bring the torch back after the slow pair arrives.

Greedy strategy

Definition A greedy strategy builds a plan one step at a time and at each step takes the option that looks best for that step alone, by a fixed rule, without looking ahead to later steps. Greedy strategies are easy to follow and sometimes give the best plan, but a choice that is cheapest now can force expensive steps later, so in general a greedy plan need not be optimal.

In plain words Do whatever is cheapest right now and never reconsider.

Example For the bridge, a natural greedy rule sends the two fastest people on the starting side across and has the fastest person on the far side bring the torch back. It gives walkers 1 and 2 for $2$ minutes, walker 1 back for $1$ , walkers 1 and 5 for $5$ , walker 1 back for $1$ and walkers 1 and 10 for $10$ , which totals $19$ minutes. Letting walker 1 escort walker 10, then walker 5, then walker 2, bringing the torch back each time, also gives

10 + 1 + 5 + 1 + 2 = 19.

Both plans pay separately for the slow crossings of walkers 5 and 10. The 17-minute schedule spends $14$ minutes on its three forward crossings instead of $17$ , and $3$ minutes on its returns instead of $2$ , so it saves $2$ minutes in all.

Optimal schedule

Definition A schedule is a sequence of legal crossings that takes everyone from the starting side to the far side. A schedule is optimal if no legal schedule has a smaller total time. Proving that a schedule is optimal means ruling out every other schedule, including long ones that send people back and forth, either by an argument that covers all of them or by an exhaustive search. For four walkers with positive times $a \le b \le c \le d$ , the optimal total is the smaller of the escort total and the shuttle total,

\begin{gathered} 2a + b + c + d, \\[0.4em] a + 3b + d. \end{gathered}

The shuttle is faster exactly when $2b < a + c$ , the two plans tie when $2b = a + c$ , and otherwise the escort is faster. For the times $1$ , $2$ , $5$ and $10$ the totals are $19$ and $17$ .

In plain words Optimal means that nothing is faster. Showing that takes an argument about every possible schedule, not just the ones that come to mind.

Example Here is why no schedule for $1$ , $2$ , $5$ and $10$ beats $17$ minutes. A forward crossing carries at most two people and a return carries at least one. With $f$ forward crossings there are $f - 1$ returns, so at most $2f - (f - 1) = f + 1$ people end up across. All $4$ must end up across, so $f \ge 3$ , and every schedule has at least three forward crossings and two returns.

Suppose first that walkers 5 and 10 never cross forward together. Then their forward crossings are different and take at least $10$ and $5$ minutes. With exactly three forward crossings, at most $6$ people go forward and at least $2$ come back, and the difference must be $4$ , so all three forward crossings carry pairs and both returns carry single walkers. Then the third forward crossing takes at least $2$ minutes and each return at least $1$ , for a total of at least $10 + 5 + 2 + 1 + 1 = 19$ . With four or more forward crossings there are at least three returns, and the total is at least $10 + 5 + 1 + 1 + 3 = 20$ .

Suppose instead that walkers 5 and 10 cross forward together, which takes $10$ minutes. If either of them ever goes back, that return takes at least $5$ minutes, and since there are at least two other forward crossings and at least one other return, each taking at least $1$ minute, the total is at least $10 + 5 + 3 = 18$ . Otherwise walkers 5 and 10 never go back, so each of them crosses only once, in the joint crossing, and every other crossing uses only walkers 1 and 2. Their joint crossing is not the last one, because walkers 1 and 2 would then have to be across already, while the return just before it, which brought the torch back, was made by one of them. So a return follows it, made by walker 1 or walker 2 from the far side. The joint crossing is not the first one either, since walker 5 or walker 10 would then have to make the return after it. So a return also comes just before it. Whoever makes the return after the joint crossing was on the far side during it, and whoever made the return before it was on the starting side, so these two returns are made by different walkers, one by walker 1 and the other by walker 2. Together they take at least $1 + 2 = 3$ minutes. Walker 2 has to cross forward before making a return and again after it, and each of these two forward crossings takes at least $2$ minutes. This case therefore takes at least

10 + 3 + 2 + 2 = 17

minutes. In every case the total is at least $17$ , and the schedule above takes exactly $17$ , so it is optimal.

Exhaustive search

Definition An exhaustive search solves a problem by examining every candidate in a finite list that is known to contain a best answer, so that the best candidate found is the best overall. For a puzzle the list can be all of its states together with the legal moves between them. The search is valid only if the list really covers every possibility, so when a puzzle allows plans of any length, one needs a reason why a finite list is enough.

In plain words Check every possibility, leave nothing out, and the best one found is the best there is.

Example Each walker is on one side or the other and so is the torch, so the bridge has $2^4 \cdot 2 = 32$ states. A schedule can be made as long as you like by sending people back and forth, but if a schedule comes back to a state it has visited before, deleting the crossings in between gives a legal schedule that is faster, because every crossing takes at least a minute. So an optimal schedule never repeats a state, and there are only finitely many schedules of that kind. For these four walkers there are $73{,}644$ of them, with between $5$ and $17$ crossings. Checking every one shows that exactly two take $17$ minutes, none takes $18$ and six take $19$ . A computer usually skips the listing and finds the cheapest path through the $32$ states directly, which gives the same $17$ .

The schedules with exactly five crossings can be checked by hand. Each of them sends a pair forward three times and a single walker back twice, so there are $6 \cdot 2 \cdot 3 \cdot 3 = 108$ of them, from $6$ choices of the first pair, $2$ of the first returner, $3$ of the second pair and $3$ of the second returner, after which the last pair is fixed. The same two schedules are the only ones among them that take $17$ minutes.

Check yourself

The 17-minute schedule uses walker 1 for the first return and walker 2 for the second. Find a schedule with the returns the other way round and find its total time.

Show the answer

Walkers 1 and 2 cross in $2$ minutes, and walker 2 brings the torch back in $2$ . Walkers 5 and 10 cross in $10$ , joining walker 1, who has been waiting on the far side, and walker 1 brings the torch back in $1$ . Walkers 1 and 2 cross together in $2$ . The total is

2 + 2 + 10 + 1 + 2 = 17

minutes, so this schedule is optimal too. By the exhaustive search, these two schedules are the only optimal ones.

Replace walker 2 by a walker who takes $4$ minutes, so the times are $1$ , $4$ , $5$ and $10$ . Which plan is faster now, the escort or the shuttle, and what is the least total time?

Show the answer

The escort plan takes $10 + 1 + 5 + 1 + 4 = 21$ minutes. The shuttle plan takes $4 + 1 + 10 + 4 + 4 = 23$ minutes, because the second walker now makes a slow return and crosses forward twice. By the rule for four walkers the least total is the smaller one, $21$ minutes. The test $2b < a + c$ now reads $8 < 6$ , which is false, so the shuttle no longer helps. Here the greedy rule described above is optimal, since it also takes $4 + 1 + 5 + 1 + 10 = 21$ minutes. More generally, keep the other times at $1$ , $5$ and $10$ and let the replacement walker take $b$ minutes with $1 \le b \le 5$ , so that it stays second fastest. The test reads $2b < 6$ , so the shuttle wins when $b < 3$ , the two plans tie at $20$ minutes when $b = 3$ , and the escort wins when $b > 3$ .

Extend the puzzle with a fifth walker who takes $20$ minutes, so the times are $1$ , $2$ , $5$ , $10$ and $20$ . Find a schedule that takes $33$ minutes and compare it with the greedy rule.

Show the answer

Use the shuttle for the two slowest walkers first. Walkers 1 and 2 cross in $2$ minutes, walker 1 returns in $1$ , walkers 10 and 20 cross in $20$ , and walker 2 returns in $2$ . After these $25$ minutes walkers 10 and 20 are across, and walkers 1, 2 and 5 are on the starting side with the torch. Then walkers 1 and 5 cross in $5$ , walker 1 returns in $1$ , and walkers 1 and 2 cross in $2$ , which adds $8$ minutes. The total is

25 + 8 = 33

minutes. The greedy rule takes $2 + 1 + 5 + 1 + 10 + 1 + 20 = 40$ minutes, and so does letting walker 1 escort everyone. An exhaustive search of the $2^5 \cdot 2 = 64$ states confirms that no schedule for these five walkers takes less than $33$ minutes.