一、问题
漆黑的夜里，四位旅行者来到了一座狭窄且没有护栏的小桥。如果不借助手电筒的话，大家是无论如何也不敢过桥的。不幸的是，四人一共只带了一只手电筒，而桥窄小得只够让两个人同时通过。如果各自单独过桥的话，四人耗时分别是1 2 5 10 min；如果两人同时过桥，由于互不影响，耗时就是较慢的那一个。问题来了，怎样设计一个方案，让这四个人尽可能快地过桥呢？
二、正解
假设四人为A=1、B=2、C=5、D=10
- A+B→
- A←
- C+D→
- B←
- A+B→
耗时为2+1+10+2+2=17 min
此法的聪明之处，在于让两个走得慢的人同时过桥，这样来耗时便只是走得最慢的那个D，而走得次慢的那位C就不用另花时间过桥了。
三、新解
为了自圆其说，我们先作三点假设：
- 桥是直的；
- 手电筒是LED的；
- 走最快的A在黑夜中灯光下步行速度最大为1 m/s
证明假设是成立的：
- 桥，不论是独木桥、铁索桥还是钢筋混凝土，一般都不会拐弯；
- 四位旅行者这组团闯山，必是资深驴友，LED强光手电筒必备；
- 普通人日间步行速度约0.75 m/s，夜间在灯光指引下步行速度必大大减缓，而A较D快了有10倍，定不是普通人，不防设A在手电灯光下夜间步行速度最大为1 m/s
以A=1 m/s的最大夜行速度衡算，桥的长度L=1*60=60 m；普通的LED手电筒有效射程至少200 m，对付小桥是绰绰有余。
让A和D先过桥，由D拿着手电照向前方，A则在灯光下安全过桥。当A过桥后，D站在桥上原地不动，并将手电筒照向上桥方向，B迎着灯光灯光朝D走去，与D相遇，一起过桥。当B过桥后，D原地不动等着C来，后一起过桥。任务完成。
示意如下，其中（）为灯光朝向，←↓→为运动方向：
- D→ == A→
- B→ == D↓
- D→ == B→
- C→ == D↓
- D→ == C→
- D→ ==
算法见下：
A和D一起过桥，A走完了1L，D走了1/10L；D在1/10L处等着B，见面后B又走了9/10L，D走了9/50L；D在14/50L处等着C，见面后C又走了36/50L，D走了36/100L；
以上ABC一个挨着一个过桥，一共花去1+2+5=8 min
D在64/100L处，独自走完最后36/100L，花去3.6 min；
以上四人过桥一共花去8+3.6=11.6 min，远小于17 min
此法的机智之处在于，最大程度地利用了桥的空间和手电筒的射程，最低限度地满足了问题的要求，基于实际合理的人物设定，从而得出了最终答案。
四、后记
笔者时隔两个月多回看这篇文章（之前在新浪博客上发表过），再加上之前有同学质疑，发现了两个问题：
- 为什么在新解中是D和A先走，而不是D和C先走？
- 为什么不能四个人一个紧挨着一个，一起走，D在最后打着手电给前面仨指路？
想了想该如何回答：
- D+ABC和D+CBA的耗时是一样的；
- 后面的人会挡着光，前面的A将没有足够的光前行；另外，小桥不能同时承载三个人通过；
其实是有些牵强的，不过不必那么认真。
网友评论