INKWIRE(7) reasoning puzzles INKWIRE(7)
bridge-and-torch
桥与火把
四个人，一支火把，十七分钟。
名称
题目
夜里，四个人来到一座绳桥前。他们只有一支火把，而这座桥朽烂到没有火把就无法通过。桥上最多同时站两个人，两人同行时必须按较慢者的速度前进。
四人的过桥时间分别是 1、2、5、10 分钟。每完成一次向前穿越，必须有人把火把带回来，因为火把不会自己离开桥。请给出四人全部到达对岸的最短总时间。
最显而易见的方案要 19 分钟。它不是最优解，而它为什么不是最优解，正是这道题的全部意义。
信号
条件与每个条件所强制的结论
| # | 条件 | 它强制了什么 |
|---|---|---|
| 1 | 只有一支火把，每次过桥都必须携带 | 任何载两人的向前穿越，都必须由一次载一人的返回偿还；所以行程是「往返成对 + 最后一次单向」 |
| 2 | 桥最多容纳两人 | 你不可能先把三个人积累到对岸再派一人返回——对岸必须始终留人才能把火把送回来 |
| 3 | 两人同行按慢者计速 | 最慢的两人（5 与 10）应当一起过桥而不是分开过，这样 10 分钟的代价只付一次而不是两次 |
| 4 | 最快的人是 1 和 2 | 快的人不是用来「护送」慢的人，他们的作用是廉价地来回运送火把 |
| 5 | 需要打破的预算线是 19 分钟 | 要低于 19，必须把 10 分钟段和 5 分钟段各从两次降到一次 |
例子
解题法
数穿越次数而不是数人：n 个人需要 2n−3 次单向行程（n=4 即 5 次），然后把最慢的一对安排在那一次最长的行程上。
[+] 完整解法 3
1 和 2 一起过去：2 分钟。1 带火把回来：1 分钟。5 和 10 一起过去：10 分钟。2 带火把回来：2 分钟。1 和 2 再一起过去：2 分钟。合计 2 + 1 + 10 + 2 + 2 = 17 分钟。
真正省下时间的一步是让最慢的两人配对。在朴素方案里，10 分钟那位要过去、回来、再过去，一个人就吃掉 25 分钟的桥面时间。配对之后，10 分钟的代价只付一次，而且不必再付第二次。
配对的代价是：对岸必须事先留着一个快的人把火把送回来。这就是为什么第二次是 1 和 2 一起过去而不是 1 独自过去——你必须把两个快的人都送到对岸，才能用两次廉价的返回夹住那次昂贵的穿越。
近亲条目
- [P] twelve-coin 有一枚假币，但不知道它偏重还是偏轻。
- [P] census 所有人都早已知道，但不说出口就什么事都不会发生。
- 目录 — /zh/t/puzzle/
[+] 补充与常见疑问 3
- 怎么知道 17 分钟是最优，而不只是「还不错」？
- 四个人必须有五次单向行程：三次向前、两次返回，因为移动 4 人需要 7 个单向座位，而每次返回都浪费一个座位。10 分钟那位至少要过桥一次，载他的那趟至少要花 10 分钟；5 分钟那位同样至少过桥一次。两次返回至少花掉 2 和 1 分钟。如果 5 与 10 分开走，光是这两人就要付 15 分钟，再加上至少 3 分钟的返回，已经超过 17，因此他们必须配对。
- 为什么大多数人第一反应是 19 分钟那个方案？
- 因为它把最快的人当成「可复用的资源」，而不是「需要重新部署的摆渡人」。复用最快的人让每次返回都最便宜，却把最大的那笔向前穿越开销留成了双份。
- 换成别的时间，答案会变吗？
- 会，而且这个临界点值得记住。只有当第二慢的人显著慢于最快的两人时，「最慢两人配对」才占优。若四人时间是 1、2、3、4，护送策略得 11 分钟，反而优于配对的 12 分钟。
适用范围 — 本题用于推理练习；17 分钟方案可由上面的下界论证验证。