INKWIRE(7) reasoning puzzles INKWIRE(7)
bridge-and-torch
The Bridge and the Torch
Four people, one torch, seventeen minutes.
NAME
Problem
Four people reach a rope bridge at night. They have one torch and the bridge is too rotten to cross without it. At most two people can be on the bridge at once, and when two cross together they must move at the speed of the slower one.
Crossing times are one, two, five and ten minutes. The torch must be carried back by someone after each forward crossing, because it never leaves the bridge. What is the shortest total time in which all four can be on the far side?
The obvious plan takes nineteen minutes. It is not optimal, and the reason it is not optimal is the whole point of the puzzle.
SIGNALS
Conditions and what each one forces
| # | Condition | What it forces |
|---|---|---|
| 1 | One torch, needed on every crossing | Any forward trip carrying two people must be repaid by a return trip carrying one, so crossings come in pairs plus a final forward trip |
| 2 | Bridge holds at most two people | You can never bank three people on the far side and send one back — the far side must hold at least one person to return the torch |
| 3 | A pair moves at the slower member's pace | The two slowest people (5 and 10) should cross together, not separately, so the 10-minute cost is paid once instead of twice |
| 4 | The fast people are 1 and 2 | The fastest people are not there to carry the slow ones; they are there to run the torch back and forth cheaply |
| 5 | Total budget to beat is 19 minutes | Beating 19 requires cutting the 10-minute and 5-minute crossings down from two each to one each |
EXAMPLES
Method
Count crossings, not people: 2n−3 one-way trips for n people (n=4 gives five trips), then assign the slowest pair to the single longest trip.
[+] Worked solution 3
Send 1 and 2 across together: 2 minutes. Send 1 back with the torch: 1 minute. Send 5 and 10 across together: 10 minutes. Send 2 back with the torch: 2 minutes. Send 1 and 2 across again: 2 minutes. Total 2 + 1 + 10 + 2 + 2 = 17 minutes.
The move that buys the saving is pairing the two slowest people. Under the naive plan the 10-minute walker crosses, returns, and crosses again — 25 minutes of bridge time spent on one person. Paired once, the ten-minute cost is paid once and never returns.
The price of that pairing is that a fast person must be waiting on the far side to bring the torch back. That is why the second crossing is 1 and 2 together, not 1 alone: you need both of them out there to run the two cheap returns that bracket the expensive crossing.
Kindred entries
- [P] twelve-coin One coin is counterfeit and you do not know if it is heavy or light.
- [P] census Everyone already knows, and yet nothing happens until it is said aloud.
- index — /t/puzzle/
[+] Notes and objections 3
- How do you know 17 is optimal rather than just good?
- With four people there must be five one-way trips: three forward and two returns, since 7 one-way seats are needed to move 4 people and each return wastes one seat. The 10-minute person must traverse at least once, and whichever trip carries them costs at least 10; the 5-minute person must traverse at least once too. The two returns cost at least 2 and 1. Any schedule in which 5 and 10 travel separately pays 15 minutes for the two of them plus at least 3 for returns, which already exceeds 17, so they must be paired.
- Why is the naive plan the one people pick first?
- Because it treats the fastest walker as a resource to be reused rather than a shuttle to be repositioned. Reusing the fastest person minimises the cost of each return trip, but leaves the largest forward trip unpaid once over.
- Does the answer change with different times?
- Yes, and the switch is worth knowing. Pairing the slowest two wins only when the second-slowest is much slower than the fastest two. For times 1, 2, 3, 4, the escort strategy gives 11 minutes and beats pairing, which gives 12.
Scope — Puzzle presented for practice; the 17-minute schedule is verifiable by the lower-bound argument above.