【躲避僵尸 - 过桥问题】- 有意思的数学 06

正文

你深山实验室实习, 只是好奇心作祟, 而拉下一个画着骷髅头的控制杆, 结果放出来了囚禁在实验室里的一群僵尸. 但现在可不是后悔的时候, 因为你和你的同事们得赶紧摆脱这群夺门而出僵尸.

与你逃亡的还有：门卫、助理和老教授, 一共 4 人.

你们暂时甩开了僵尸，但前方只有一条路横跨大峡谷的吊桥,

你过桥需要 1 分钟, 助理需要2 分钟, 门卫慢一点，需要 5 分钟教授需要整整 10 分钟, 因为他每走一步都紧紧抓住绳索.

教授计算出来仅仅在17分钟之后，僵尸就会追上你们, 所以只有这么多时间让所有人过桥并剪断绳索.

但问题是，吊桥只能承载 2 个人的重量, 更糟糕的是已经是深夜一片漆黑，眼前伸手不见五指, 而你们一路提着的只有一盏灯, 仅仅也只能照亮面前的一小块地方.

你能想出一个方案，让所有人及时逃脱吗? 请记住下面解决过桥问题的要求：

吊桥每次只能承载最多 2 个人的重量;

任何人在桥上时必须要么提着灯，否则就掉落深渊;

任何人都可在峡谷两侧的黑暗中安全等待其他人;

最重要的是，所有人必须在僵尸到达之前安全通过吊桥, 否则，当僵尸走上桥时，如果有人还在上面最后，桥可承受不了这重量;

这里不能使用任何花招 - 不能荡过去, 不能把桥用作木筏, 不能和僵尸做朋友;

如果你想尝试解决问题找出答案的话, 请马上暂停往下翻.

答案揭晓: 起初似乎无论怎么安排都得超出 1~2 分钟，但可行的方案是存在的.

最关键的想法是缩短最慢的两个人所花费的时间, 这可通过让他们一起过桥来实现. 同时因为需要有人提着灯返回, 所以必须让速度最快的人来完成这个任务.

4 人过桥所花费时间, 用ABCD从左往右分别表示

综上，首先助理(A)和你( )提着灯快跑过桥, 虽然你必须为她而放慢一点脚步, 但2分钟后，你俩都过桥了. 速度最快的你提着灯跑回去, 现在仅仅过了1分钟.

目前为止，一切顺利. 现在最耗时的部分来了, 门卫(C)和教授(D)接过灯一起过桥, 因为门卫必须为教授放慢脚步, 所以这得用10 分钟的时间.

现在已经过去 3 + 10 =13分钟了.

那僵尸只距离你4分钟的路程了, 可你仍呆在危险的一侧, 不过助理在另一侧已经等候多时了, 她可是在四人中速度排名第二.

所以她从门卫手中接过灯, 花2分钟跑过桥, 回到你那侧的时候, 时间只剩2分钟，刚好够你俩最后一次过桥的时间.

当你一踏上峡谷的另一侧就立即剪断绳索，摧毁身后的吊桥, 这样时间刚刚好过去17分钟.

解决此类过桥问题的最佳方案, 解决思路是必须安排最快的分到一组，最慢的分到一组, 这样分类下来才会达到最优解.

或者可以将此类问题转成图论问题来解决, 用 Dijkstra 算法很容易求出其最短路径, 感兴趣的朋友可以再考虑一下.

根据有关 TED Ed 视频: The Infinite Hotel Paradox 及维基百科编写. 完整视频与字幕, 微信后台回复关键字 [TED] 得到国内云盘下载地址. 更多 TED Ed 视频见下图或未来继续推出的文章.